Polynomial hierarchy (nonfiction): Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| 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, NP and co-NP to 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 [[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 19: | Line 19: | ||
* [[Arithmetical hierarchy (nonfiction)]] | * [[Arithmetical hierarchy (nonfiction)]] | ||
* [[Complexity class (nonfiction)]] | * [[Complexity class (nonfiction)]] | ||
* [[Computation (nonfiction)]] | |||
* [[co-NP (nonfiction)]] | |||
* [[Exponential hierarchy (nonfiction)]] | * [[Exponential hierarchy (nonfiction)]] | ||
* [[EXPTIME (nonfiction)]] | * [[EXPTIME (nonfiction)]] | ||
| Line 25: | Line 27: | ||
* [[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 33: | Line 39: | ||
[[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)]] | ||
Revision as of 12:55, 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)
- 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