Clay Millennium Problem

P versus NP

Open

The solver below decides every 2-SAT instance in linear time. That is a polynomial algorithm, and it always returns yes or no.

It does not decide 3-SAT. Width-two clauses become implications; width-three clauses do not. Whether some other polynomial decides an NP-complete problem is the Clay question, and it is still open.

NPWitness, checked in polynomial time

Decided outright, in polynomial time. Contained in NP.

The gap, if there is one

NP-complete problems live here only if P ≠ NP. A polynomial algorithm for any one of them empties the gap.

Posed: Cook, 1971. Levin, independently.
Prize: One million dollars, either direction.
Not this release: openai/math family 102 is Max-Cut hardness, not a separation.

01 — Solver

Resolves in polynomial time

This explorer is a decision procedure for 2-SAT. Each clause of width two becomes two implications. Strongly connected components of that graph decide the formula. The work is linear in variables plus clauses: a polynomial of degree 1. It always answers.

Variables8Clause density2.5Seed4

A hidden assignment is planted, so the solver must find a witness.

2-SAT · Aspvall–Plass–Tarjan

n = 8 · m = 20 · O(n + m)

Satisfiable

Operations: 200
Ops / (n+m): 7.14
Components: 6
Degree: 1

Decided satisfiable after 200 graph steps. The witness below satisfies every clause. The same procedure decides an unsatisfiable formula; there is no separate exponential search.

x1 1

x2 0

x3 1

x4 1

x5 0

x6 0

x7 0

x8 0

Implications

¬x6 → ¬x7
x7 → x6
x8 → x5
¬x5 → ¬x8
¬x4 → ¬x6
x6 → x4
x4 → x3
¬x3 → ¬x4

32 further implications are in the graph and were searched.

02 — 3-SAT

Where the polynomial stops

3-SAT is NP-complete. The linear solver above does not apply: a clause of three literals is not a pair of implications. Naive search and DPLL still decide these small instances. Neither is known to be polynomial on every instance.

Variables10Clause density4.2Seed3Search budget80,000

A hidden assignment is planted, so a witness exists.

Planted 3-SAT · Naive

n = 10 · m = 42 · m/n = 4.20

Witness checks

Tried: 760
Decisions: 760
Unit props: 0
Checker ops: 82

Naive search tried 760 assignments. The checker accepted the witness in 82 literal reads. Switch to DPLL and solve again to watch the search shrink.

Witness bits. Tap one to break it.

1¬x1 ∨ ¬x8 ∨ x5
2¬x7 ∨ ¬x3 ∨ x6
3¬x9 ∨ x4 ∨ ¬x10
4x2 ∨ x4 ∨ x8
5¬x9 ∨ ¬x7 ∨ x8
6x4 ∨ x6 ∨ x9
7¬x6 ∨ x8 ∨ ¬x9
8¬x7 ∨ ¬x5 ∨ x10
9¬x8 ∨ x1 ∨ ¬x6
10¬x3 ∨ x5 ∨ ¬x6
11¬x2 ∨ ¬x10 ∨ x7
12¬x5 ∨ ¬x2 ∨ x7
13¬x10 ∨ x6 ∨ x9
14x10 ∨ ¬x4 ∨ ¬x6
15¬x3 ∨ x9 ∨ x1
16x9 ∨ x1 ∨ ¬x7
17x6 ∨ ¬x2 ∨ ¬x1
18x9 ∨ x7 ∨ ¬x2
19x7 ∨ ¬x6 ∨ x8
20x10 ∨ x2 ∨ ¬x4
21x3 ∨ ¬x7 ∨ x1
22x5 ∨ x4 ∨ x10
23¬x2 ∨ x9 ∨ x8
24x4 ∨ x3 ∨ x2
25x1 ∨ ¬x6 ∨ ¬x5
26x10 ∨ x3 ∨ ¬x4
27¬x1 ∨ x2 ∨ ¬x4
28x2 ∨ ¬x6 ∨ x9
29¬x1 ∨ ¬x5 ∨ x7
30¬x7 ∨ ¬x9 ∨ ¬x3
31¬x2 ∨ ¬x6 ∨ x3
32x9 ∨ ¬x7 ∨ ¬x4
33¬x5 ∨ x9 ∨ ¬x4
34¬x3 ∨ ¬x8 ∨ x5
35x4 ∨ ¬x3 ∨ x1
36x3 ∨ x8 ∨ ¬x9
37¬x9 ∨ x8 ∨ ¬x1
38x9 ∨ x8 ∨ ¬x5
39¬x6 ∨ ¬x7 ∨ x1
40x10 ∨ ¬x9 ∨ x1
41x6 ∨ ¬x9 ∨ ¬x8
42¬x2 ∨ x1 ∨ x4

03 — Scaling

The same algorithm, larger inputs

Each point is one real run of the solver on a random 2-SAT instance with three clauses per variable. Operations divided by n + m stay between 7.00 and 7.01. A bounded ratio is a polynomial of degree 1. The straight fit is that constant times n + m.

Operations measuredDegree-1 fit

n	Ops	/(n+m)	Time
40	1,121	7.01	—
80	2,241	7.00	—
160	4,481	7.00	—
240	6,721	7.00	—
320	8,961	7.00	—

04 — Cover

A cover you can check by hand

Vertex cover is NP-complete. Pick vertices until every edge touches the set. The checker walks the 16 edges. Deciding whether any cover of size at most k exists, by brute force, walks the power set of 9 vertices — 512 subsets. The smallest cover here has size 6.

Your set

Not a cover. 16 edges stay uncovered, found in 16 reads.

Budget k6

11 covers of size ≤ 6. Counting them looks at all 512 subsets. Checking the set you picked looks at 16 edges.

05 — Why open

The laboratory does not close the question

The question

P is the class of decision problems a deterministic machine can settle in time bounded by a polynomial in the length of the input. NP is the class of decision problems whose yes-instances have a witness, also polynomially long, that a deterministic machine can check in polynomial time. P sits inside NP, because a decider can ignore any witness it is handed. The Clay problem asks whether the containment is equality.

P  ⊆  NP
P  =  NP   or   P  ≠  NP
one NP-complete problem in P
  ⇒  every problem in NP is in P

Cook and Levin proved satisfiability NP-complete in 1971. The special case of clauses of width two is not. Aspvall, Plass, and Tarjan (1979) decide 2-SAT from the strongly connected components of its implication graph, in time linear in the size of the formula. That is the algorithm running in the solver above. A clause of width three does not split into two implications, and no rewrite of that graph argument is known to absorb the third literal. Karp’s reductions put vertex cover in the same completeness class as 3-SAT. The instance you can still solve by hand is the problem, at a size a browser can finish. It is not in the polynomial fragment.

What would count

A polynomial-time algorithm for any NP-complete problem, together with a proof of correctness and an explicit polynomial bound.
Or a proof that some NP-complete problem admits no polynomial-time algorithm.

Finite timing curves do not count. A language model’s manuscript does not count until the argument is correct. A huge polynomial, were one found, would settle the mathematical question and might still be useless in practice. Cryptography cares about feasible exponents, not only about the existence of some exponent.

Three barriers a proof has to face

Relativization. Baker, Gill, and Solovay (1975) built oracles A and B with P^A = NP^A and P^B ≠ NP^B. Any argument that treats the machine as a black box, and would still go through if that machine had an arbitrary oracle, cannot decide the unrelativized question.
Natural proofs. Razborov and Rudich (1997) showed that a broad, “natural” style of circuit lower bound would also break cryptographic pseudorandomness. The usual route toward P ≠ NP — prove SAT needs superpolynomial circuits — is blocked for that style of proof, if strong pseudorandom generators exist.
Algebrization. Aaronson and Wigderson (2008) extended the oracle barrier to algebraic oracles. Several techniques that escape relativization, including arithmetization, still algebrize, and algebrizing techniques do not separate P from NP.

The working conjecture in complexity theory is P ≠ NP. That is a consensus about where the proof will land, not a proof. Ladner’s theorem says that if the classes differ, then some problems in NP are neither in P nor NP-complete. The landscape can be richer than the two headlines.

The nearest page in openai/math

On 6 October 2026 OpenAI published github.com/openai/math: 722 manuscripts in 372 families, written by an unreleased internal model, average compute about three hours of ChatGPT Pro thinking, Apache-2.0. The repository says outright that verification is uneven, not every paper has a Lean formalization, and some unformalized results could have issues.

The complexity headline in that catalogue is family 102, “Ordinary NP-hardness at the basic semidefinite threshold,” with the preprint A Direct Proof of Optimal Max-Cut Hardness (23 September 2026). The claim, as titled, is approximation hardness: it is NP-hard to approximate Max-Cut better than the Goemans–Williamson ratio, about 0.878, matching the semidefinite program from 1995. Read as a reduction, that says a better polynomial-time approximation would collapse P and NP. It does not exhibit such an algorithm, and it does not prove that none exists. It is downstream of the Millennium problem. It is not a solution of it. This page has not checked the preprint’s proof.