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:
“Major [William] McKinley visited me. He is on a stumping tour.... I criticized the bloody-shirt course of the canvass. It seems to me to be bad “politics,” and of no use.... It is a stale issue. An increasing number of people are interested in good relations with the South.... Two ways are open to succeed in the South: 1. A division of the white voters. 2. Education of the ignorant. Bloody-shirt utterances prevent division.”
—Rutherford Birchard Hayes (1822–1893)
“There were three classes of inhabitants who either frequent or inhabit the country which we had now entered: first, the loggers, who, for a part of the year, the winter and spring, are far the most numerous, but in the summer, except for a few explorers for timber, completely desert it; second, the few settlers I have named, the only permanent inhabitants, who live on the verge of it, and help raise supplies for the former; third, the hunters, mostly Indians, who range over it in their season.”
—Henry David Thoreau (1817–1862)
“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)