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 |
||
| 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]]. | 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 the News == | == In the News == | ||
| Line 16: | Line 16: | ||
== Nonfiction cross-reference == | == Nonfiction cross-reference == | ||
* [[Analytical hierarchy (nonfiction)]] | |||
* [[Arithmetical hierarchy (nonfiction)]] | |||
* [[Complexity class (nonfiction)]] | |||
* [[Exponential hierarchy (nonfiction)]] | |||
* [[EXPTIME (nonfiction)]] | |||
* [[Hierarchy (mathematics) (nonfiction)]] | |||
* [[Mathematical logic (nonfiction)]] | * [[Mathematical logic (nonfiction)]] | ||
* [[Mathematician (nonfiction)]] | * [[Mathematician (nonfiction)]] | ||
Revision as of 08:34, 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)
- Exponential hierarchy (nonfiction)
- EXPTIME (nonfiction)
- Hierarchy (mathematics) (nonfiction)
- Mathematical logic (nonfiction)
- Mathematician (nonfiction)
- Mathematics (nonfiction)
External links:
- Polynomial hierarchy @ Wikipedia