В теории сложности вычислений, то класс сложности PH является объединением всех классов сложности в полиномиальной иерархии :
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.