Math 2.0

Computer science Computational complexity: resources and classes Problem

P versus NP problem

Builds on PNPNP-completenessBoolean satisfiability problemCook–Levin theoremco-NP

Problem

Let P be the class of languages decided by deterministic Turing machines in polynomial time. Let NP be the class of languages decided by nondeterministic Turing machines in polynomial time. The problem asks whether P=NP\mathrm{P} = \mathrm{NP}.

Remarks

The problem is open. It is one of the seven Millennium Prize Problems of the Clay Mathematics Institute. The inclusion P⊆NP\mathrm{P} \subseteq \mathrm{NP} is easy, so the question is whether every language in NP lies in P\mathrm{P}. By the Cook–Levin theorem, P=NP\mathrm{P} = \mathrm{NP} holds exactly when SAT lies in P\mathrm{P}. More generally, it holds exactly when some NP-complete problem lies in P\mathrm{P}. If P=NP\mathrm{P} = \mathrm{NP}, then NP is closed under complement, so NP equals co-NP. Most researchers expect that P≠NP\mathrm{P} \ne \mathrm{NP}. Several known proof methods cannot settle the question, among them relativization, natural proofs and algebrization.

Reading path

To understand this page from the ground up, read these 18 pages in order. The foundations come first.

Show the path as a graph
Conjunctive normal form, concept, no evidence levelConjunctive normal fo…conceptNP, concept, no evidence levelNPconceptNP-completeness, concept, no evidence levelNP-completenessconceptNondeterministic Turing machine, concept, no evidence levelNondeterministic Turi…conceptP, concept, no evidence levelPconceptPolynomial-time reduction, concept, no evidence levelPolynomial-time reduc…conceptProposition, concept, no evidence levelPropositionconceptSatisfiability, concept, no evidence levelSatisfiabilityconceptco-NP, concept, no evidence levelco-NPconceptConjunction, definition, no evidence levelConjunctiondefinitionDisjunction, definition, no evidence levelDisjunctiondefinitionImplication, definition, no evidence levelImplicationdefinitionNegation, definition, no evidence levelNegationdefinitionBiconditional, definition, no evidence levelBiconditionaldefinitionPropositional logic, concept, no evidence levelPropositional logicconceptBoolean satisfiability problem, problem, no evidence levelBoolean satisfiabilit…problemCook–Levin theorem, statement, no evidence levelCook–Levin theoremstatementP versus NP problem, problem, no evidence levelP versus NP problemproblem
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Conjunctive normal form concept
  2. NP concept
  3. NP-completeness concept
  4. Nondeterministic Turing machine concept
  5. P concept
  6. Polynomial-time reduction concept
  7. Proposition concept
  8. Satisfiability concept
  9. co-NP concept
  10. Conjunction definition
  11. Disjunction definition
  12. Implication definition
  13. Negation definition
  14. Biconditional definition
  15. Propositional logic concept
  16. Boolean satisfiability problem problem
  17. Cook–Levin theorem statement
  18. P versus NP problem problem

Further reading

  1. Web https://en.wikipedia.org/wiki/P_versus_NP_problem
About this page
TagMFN5GYZH5Z
URIm2://MFN5GYZH5Z
Kindproblem
WritingW0 stub
MSC68Q15, 68Q17
StatusThis copy of the site has no build data. Run m2 status MFN5GYZH5Z.
AboutP, NP
UsesP, NP, NP-completeness, Boolean satisfiability problem, Cook–Levin theorem, co-NP
Same as
Changed3 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

Results about this