Polynomial hierarchy (nonfiction): Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (One intermediate revision 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 (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]]. | [[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 20: | Line 20: | ||
* [[Complexity class (nonfiction)]] | * [[Complexity class (nonfiction)]] | ||
* [[Computation (nonfiction)]] | * [[Computation (nonfiction)]] | ||
* [[Computational complexity (nonfiction)]] | |||
* [[co-NP (nonfiction)]] | * [[co-NP (nonfiction)]] | ||
* [[Exponential hierarchy (nonfiction)]] | * [[Exponential hierarchy (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