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

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

${\ 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