PH (complexity)
Class in computational complexity theory / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about PH (complexity)?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy:
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 = PPP and PSPACE.
PH has a simple logical characterization: it is the set of languages expressible by second-order logic.