PH (сложность)

редактировать

В теории сложности вычислений, то класс сложности PH является объединением всех классов сложности в полиномиальной иерархии :

п ЧАС знак равно k N Δ k п {\ displaystyle \ mathrm {PH} = \ bigcup _ {k \ in \ mathbb {N}} \ Delta _ {k} ^ {\ mathrm {P}}}

PH был впервые определен Ларри Стокмейером. Это частный случай иерархии ограниченной переменной машины Тьюринга. Он содержится в P #P = P PP (по теореме Тоды ; класс задач, которые разрешимы машиной Тьюринга с полиномиальным временем с доступом к #P или, что эквивалентно, PP оракулу ), а также в PSPACE.

PH имеет простую логическую характеристику : это набор языков, выражаемых логикой второго порядка.

PH содержит почти все известные классы сложности внутри PSPACE ; в частности, он содержит P, NP и co-NP. Он даже содержит вероятностные классы, такие как BPP и RP. Однако есть некоторые свидетельства того, что BQP, класс задач, решаемых за полиномиальное время с помощью квантового компьютера, не содержится в PH.

P = NP тогда и только тогда, когда P = PH. Это может упростить возможное доказательство того, что P ≠ NP, поскольку необходимо только отделить P от более общего класса PH.

Рекомендации
Общие ссылки
  • Бюргиссер, Питер (2000). Полнота и редукция теории алгебраической сложности. Алгоритмы и вычисления в математике. 7. Берлин: Springer-Verlag. п. 66. ISBN   3-540-66752-0. Zbl   0948.68082.
  • Зоопарк сложности : PH

  • v
  • т
  • е
Последняя правка сделана 2024-01-08 07:58:32
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте