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 between, 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)
“In the relations of a weak Government and a rebellious people there comes a time when every act of the authorities exasperates the masses, and every refusal to act excites their contempt.”
—John Reed (1887–1920)
“... too much attention is paid to dress by those who have neither the excuse of ample means nor of social claims.... The injury done by this state of things to the morals and the manners of our lower classes is incalculable.”
—Mrs. H. O. Ward (1824–1899)
“In a hierarchy every employee tends to rise to his level of incompetence.”
—Laurence J. Peter (1919–1990)