Polynomial hierarchy (nonfiction): Difference between revisions
Jump to navigation
Jump to search
(Created page with "In computational complexity theory, the '''polynomial hierarchy''' (sometimes called the '''polynomial-time hierarchy''') is a...") |
No edit summary |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
In [[Computational complexity theory (nonfiction)|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 (nonfiction)|mathematical logic]]. | [[File:Polynomial_time_hierarchy.svg|thumb|Commutative diagram equivalent to the polynomial time hierarchy. The arrows denote inclusion.]]In [[Computational complexity theory (nonfiction)|computational complexity theory]], the '''polynomial hierarchy''' (sometimes called the '''polynomial-time hierarchy''') is a [[Hierarchy (mathematics) (nonfiction)|hierarchy]] of [[Complexity class (nonfiction)|complexity classes]] that generalize the classes [[P (complexity) (nonfiction)|P]], [[NP (complexity) (nonfiction)|NP]] and [[co-NP (nonfiction)|co-NP]] to [[Oracle machine (nonfiction)|oracle machines]]. It is a resource-bounded counterpart to the [[Arithmetical hierarchy (nonfiction)|arithmetical hierarchy]] and [[Analytical hierarchy (nonfiction)|analytical hierarchy]] from [[Mathematical logic (nonfiction)|mathematical logic]]. | ||
== In the News == | == In the News == | ||
| Line 16: | Line 16: | ||
== Nonfiction cross-reference == | == 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)]] | * [[Mathematical logic (nonfiction)]] | ||
* [[Mathematician (nonfiction)]] | * [[Mathematician (nonfiction)]] | ||
* [[Mathematics (nonfiction)]] | * [[Mathematics (nonfiction)]] | ||
* [[NP (complexity) (nonfiction)]] | |||
* [[Oracle machine (nonfiction)]] | |||
* [[P (complexity) (nonfiction)]] | |||
* [[Turing machine (nonfiction)]] | |||
External links: | External links: | ||
| Line 27: | Line 40: | ||
[[Category:Nonfiction (nonfiction)]] | [[Category:Nonfiction (nonfiction)]] | ||
[[Category:Computation (nonfiction)]] | [[Category:Computation (nonfiction)]] | ||
[[Category:Computational complexity (nonfiction)]] | |||
[[Category:Computer science (nonfiction)]] | |||
[[Category:Mathematics (nonfiction)]] | [[Category:Mathematics (nonfiction)]] | ||
Latest revision as of 13:21, 1 September 2018
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.
In the News
Fiction cross-reference
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