PH (complexity)

In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy:

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

PH was first defined by Larry Stockmeyer.^[1] It is a special case of hierarchy of bounded alternating Turing machine. It is contained in P^#P = P^PP and PSPACE.

PH has a simple logical characterization: it is the set of languages expressible by second-order logic.