Skip to content

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

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.