Properties
The polynomial hierarchy is an analogue (at much lower complexity) of the exponential hierarchy and arithmetical hierarchy.
It is known that PH is contained within PSPACE, but it is not known whether the two classes are equal. One useful reformulation of this problem is that PH = PSPACE if and only if second-order logic over finite structures gains no additional power from the addition of a transitive closure operator.
If the polynomial hierarchy has any complete problems, then it has only finitely many distinct levels. Since there are PSPACE-complete problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse, since a PSPACE-complete problem would be a -complete problem for some k.
Each class in the polynomial hierarchy contains -complete problems (problems complete under polynomial-time many-one reductions). Furthermore, each class in the polynomial hierarchy is closed under -reductions: meaning that for a class in the hierarchy and a language, if, then as well. These two facts together imply that if is a complete problem for, then, and . For instance, . In other words, if a language is defined based on some oracle in, then we can assume that it is defined based on a complete problem for . Complete problems therefore act as "representatives" of the class for which they are complete.
Sipser–Lautemann theorem states that the class BPP is contained in second level of polynomial hierarchy.
Kannan's theorem states that for any k, is not contained in SIZE(nk).
Toda's theorem states that the polynomial hierarchy is contained in P#P.
Read more about this topic: Polynomial Hierarchy
Famous quotes containing the word properties:
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)