Relations Between Classes in The Polynomial Hierarchy
The definitions imply the relations:
Unlike the arithmetic and analytic hierarchies, whose inclusions are known to be proper, it is an open question whether any of these inclusions are proper, though it is widely believed that they all are. If any, or if any, then the hierarchy collapses to level k: for all, . In particular, if P = NP, then the hierarchy collapses completely.
The union of all classes in the polynomial hierarchy is the complexity class PH.
Read more about this topic: Polynomial Hierarchy
Famous quotes containing the words relations, classes and/or hierarchy:
“In the mythic schema of all relations between men and women, man proposes, and woman is disposed of.”
—Angela Carter (1940–1992)
“There are three classes into which all the women past seventy that ever I knew were to be divided: 1. That dear old soul; 2. That old woman; 3. That old witch.”
—Samuel Taylor Coleridge (1772–1834)
“In the world of the celebrity, the hierarchy of publicity has replaced the hierarchy of descent and even of great wealth.”
—C. Wright Mills (1916–1962)