[#P39] P versus NP
Problem. The complexity classes \(\mathsf{P}\) and \(\mathsf{NP}\) are equal. Equivalently, every decision problem with polynomial-time verifiable yes-certificates has a deterministic polynomial-time decision algorithm.
1Context
The question asks whether efficient verification always implies efficient deterministic solution.
2Problem setup
Definition 1 (P). P is the class of decision problems decidable by a deterministic Turing machine in polynomial time.
Definition 2 (NP). NP is the class of decision problems whose yes-instances admit certificates verifiable by a deterministic Turing machine in polynomial time.
Remark 1. The question asks whether efficient verification always implies efficient deterministic solution.
3What counts as a solution
- Prove P = NP by giving a polynomial-time deterministic algorithm for an NP-complete problem and proving its running time and correctness, or prove P differs from NP within the standard formal definitions.
1Status
Current status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: NP-completeness connects a polynomial-time algorithm for one NP-complete problem to all of NP. Strong lower bounds exist for restricted models, alongside formal barriers to several proof methods. Exact unresolved remainder: Determine whether every language in NP belongs to P, equivalently whether P=NP.[1][2]
1Records
Notes and companion material
Original intake status. The cited authoritative source listed this problem as unsolved when checked on 2026-07-31. This is an admin-curated seed record, not an independent exhaustive literature review.
- Consult the cited official problem description for the precise machine model, reductions, and prize conditions.
Recorded example 1. Boolean satisfiability is NP-complete, so a proven polynomial-time deterministic algorithm for it would prove P = NP.
2See also
- Complexity of equality for binary-code weight enumeratorscomputational complexity
- Unique Games conjecturecomputational complexity
- Quantum PCP conjecturecomputational complexity
How to cite
TheoremDB contributors, “P versus NP,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/p-versus-npThis page as plain text: p-versus-np.md
This problem includes 2 records joined by 2 typed links, sourced from claymath.org[1], current as of July 31, 2026.
1References
- Packet source. Clay Mathematics Institute, P vs NP, official Millennium Prize Problem page, checked 2026-08-01. Official Problem Description by Stephen Cook; listed under Unsolved Millennium Prize Problems. ↗website · primary source · checked 2026-07-31Source use: original summary.The cited authoritative source listed this problem as unsolved when checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.Also cited at Unsolved label and official overview.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.Provides the authoritative current status and links Cook's official problem description.Source named by the research packet.
- Stephen Cook, The P versus NP Problem, official Clay Mathematics Institute problem description. claymath.org checked 2026-08-01. Official problem description. ↗website · primary source · checked 2026-08-01Source use: original summary.Defines the target and foundational known results.
An original CC0 restatement prepared by TheoremDB maintainers.