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

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

${\displaystyle \mathrm {PH} =\bigcup _{k\in \mathbb {N} }\Delta _{k}^{\mathrm {P} }}$

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

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

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

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

Ссылки [ править ]

Общие ссылки [ править ]

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