Domain 07 · P versus NP
Millennium status, 20 October 2026: Clay continues to list P versus NP as Unsolved. Advances about related complexity conjectures do not establish either P = NP or P ≠ NP. Full comparison.
The question in everyday language
Some problems have answers that are easy to check even though finding an answer appears difficult. The P versus NP question asks whether every problem with efficiently checkable answers can also be solved efficiently.
A successful answer must apply to a carefully defined class of problems and to the way computational time grows with input length. A fast program for a handful of examples would not resolve the question.
GCL has organized precise definitions, useful equivalences and common mistakes in proposed proofs. What remains uncertain: no proof of P = NP or P ≠ NP has emerged from this work.
Detailed research record
Accessible research guide: PNP-001 Research Guide
New research accompaniment (November 2026): P versus NP from Above explores whether MIP* = RE verification compression can produce a transferable classical lower-bound principle. Read the educated-lay primer, technical spine, evidence register, and working preprint record. This is an exploratory approach, not a proof of P = NP or P != NP.
Research surface authority
LIVE: https://github.com/grandchallenge/MATH-PROGRAMME/issues/162
AUTHORITY: PNP-WP00-source-definition-equivalence-audit.md.
EXPOSITION: this page is the human-facing projection; the issue governs mutable research state and protected records govern admitted claims.
Campaign ID: PNP-001
Mathematical status: open problem
Programme state: WP00 source, model, and encoding dossier merged
Governance: ADR-0009
Canonical challenge
Determine whether every decision language whose YES instances admit polynomially bounded certificates verifiable in deterministic polynomial time is itself decidable in deterministic polynomial time.
The target is the exact language-theoretic proposition P = NP or its negation under uniform finite algorithms, complete encoded bit-length, total malformed-input handling, and deterministic polynomial-time many-one reductions.
Programme posture
PNP-WP00 fixes the Turing-machine model, binary encodings, resource accounting, reduction certificates, exact SAT equivalence routes, stronger sufficient statements, neighbouring complexity classes, barrier scope, and false-proof seeds.
The next documentary stages are the executable false-proof atlas and the source-normalized algorithm, lower-bound, and theorem ledger. No unrestricted algorithm or lower-bound claim is authorized by WP00.
Canonical artifacts
- WP00 integrated audit
- Charter
- Machine and encoding lock
- Merge record PR #88
- Catalogue-integration decision ADR-0009
Claim boundary
The programme has not proved P = NP or P != NP, produced a new polynomial-time algorithm for an NP-complete language, proved an unrestricted circuit or machine lower bound, established a new barrier theorem, or made a novelty claim.