Polynomial hierarchy (nonfiction)

Commutative diagram equivalent to the polynomial time hierarchy. The arrows denote inclusion.

In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic.

Fiction cross-reference

• Crimes against mathematical constants
• Gnomon algorithm
• Gnomon Chronicles
• Mathematician
• Mathematics

Nonfiction cross-reference

• Analytical hierarchy (nonfiction)
• Arithmetical hierarchy (nonfiction)
• Complexity class (nonfiction)
• Computation (nonfiction)
• Computational complexity (nonfiction)
• co-NP (nonfiction)
• Exponential hierarchy (nonfiction)
• EXPTIME (nonfiction)
• Hierarchy (mathematics) (nonfiction)
• Mathematical logic (nonfiction)
• Mathematician (nonfiction)
• Mathematics (nonfiction)
• NP (complexity) (nonfiction)
• Oracle machine (nonfiction)
• P (complexity) (nonfiction)
• Turing machine (nonfiction)

External links:

• Polynomial hierarchy @ Wikipedia