Computer science Computational complexity: resources and classes Concept
P
Summary
P is the complexity class of decision problems that a deterministic Turing machine can solve in polynomial time. It is the usual formal model of the problems that are "efficiently solvable". The class does not change if the Turing machine is replaced by any other reasonable deterministic model, such as a random-access machine. Whether P equals NP is the central open question of complexity theory.
Where this leads
35 pages build on this one.
- Christofides algorithm
- Ladner's theorem
- Boolean satisfiability problem
- Graph isomorphism problem
- L
- Constraint satisfaction problem
- Exponential time hypothesis
- Polynomial hierarchy
- Time hierarchy theorem
- Strongly polynomial algorithm for linear programming
- Baker–Gill–Solovay theorem
- Cook–Levin theorem
- NL
- Hardness of approximation
- Quadratic assignment problem
- Schaefer's dichotomy theorem
- Karp–Lipton theorem
- Lin–Kernighan heuristic
- NP-hardness of integer programming
- P versus NP problem
- co-NP
- Approximation algorithm
- One-way function
- Polynomial-time reduction
- NP-completeness
- NP
- EXPTIME
- PSPACE-completeness
- Arthur–Merlin protocol
- Vehicle routing problem
- Travelling salesman problem
- PSPACE
- Karp's 21 NP-complete problems
- Held–Karp algorithm
- Khachiyan's theorem that linear programming is in P
Further reading
About this page
| Tag | GVT2NKN37K |
|---|---|
| URI | m2://GVT2NKN37K |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q15 |
| Same as | |
| Changed | 3 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
Used by
- Ladner's theorem
- Boolean satisfiability problem
- Graph isomorphism problem
- L
- Constraint satisfaction problem
- Polynomial hierarchy
- Time hierarchy theorem
- Strongly polynomial algorithm for linear programming
- Baker–Gill–Solovay theorem
- NL
- Hardness of approximation
- Schaefer's dichotomy theorem
- P versus NP problem
- co-NP
- Approximation algorithm
- One-way function
- Polynomial-time reduction
- NP-completeness
- NP
- PSPACE-completeness
- Arthur–Merlin protocol
- Travelling salesman problem
- PSPACE
- Khachiyan's theorem that linear programming is in P