AI News

The race to solve P vs NP

P vs NP remains open as of November 21, 2026. The Clay Mathematics Institute still lists the problem as unsolved. The most consequential recent development is a pair of claims from OpenAI and Anthropic that algorithms can solve 3-SAT in subexponential time. If the proofs hold up, they would overturn a conjecture that researchers have used for decades to reason about how fast algorithms can get. The polynomial-time question at the heart of P vs NP would still be open. Clay Mathematics Institute · UC San Diego

Kingy checks for developments every 12 hours and adds dated entries when new evidence changes the story. Start with the latest developments, see what would solve the problem, or jump to the history of the search.

Latest developments in the P vs NP race

November 19, 2026 · Independent examination of the SAT claims continues

UC San Diego reported that Russell Impagliazzo and Ramamohan Paturi, two of the researchers behind the Exponential Time Hypothesis (ETH), are organizing an independent examination with MIT computer scientist Ryan Williams. Their public discussion hub invites research contributions on the algorithms and their consequences. The university report describes an examination in progress. UC San Diego update · Working group

November 17, 2026 · A complexity researcher revisits his case for P = NP

Emanuele Viola had argued for P = NP as early as 2018. He says the new algorithmic results reinforce his view that theorists have underestimated what efficient computation can do. His piece offers a researcher’s account of how the fall’s announcements changed discussions in the field. P = NP remains his prediction. Viola’s account

November 16, 2026 · A fallback for some lower bounds gets a revision

The MIT Hardness Group and coauthors revised their November 2 preprint on the Stearns–Hunt hypothesis. They argue that a weaker conjecture about SAT can preserve some results previously based on ETH, at the cost of weaker time bounds. The replacements depend on that weaker conjecture. The paper addresses the consequences of the announced algorithms, whose verification is a separate question. Preprint and revision history

November 12, 2026 · The working group publishes OpenAI’s prompt

The prompt asked for an unconditional refutation of the deterministic Strong Exponential Time Hypothesis (SETH). SETH concerns how close the best exponential rate gets to exhaustive search as the allowed clause width grows. The prompt gives researchers a record of the assignment that produced OpenAI’s ETH result. If the claimed subexponential bounds hold for every fixed clause width, they would also contradict deterministic SETH. The claims still leave the polynomial-time question open. Working group’s prompt release

November 9, 2026 · A follow-up extends the algorithmic idea

Carmen Strassle and Bernardo Subercaseaux submitted a preprint to arXiv using the SAT work to bound the cost of simulating nondeterministic computation on multitape Turing machines. Their strongest stated bound is 2O(t / √log t) time for simulating a nondeterministic computation that takes time t. The exact parameter matters. This is subexponential in the original computation time t, which may itself be a polynomial in the input length. Strassle and Subercaseaux preprint

November 6, 2026 · Formal checks connect the two SAT claims to a shared definition

Carlos Toledo reported that Lean checked separate links from each lab’s formal result to a refutation of ETH as defined for ComplexityLib’s multitape Turing machine. That puts both results in a common formal setting. Relating the library’s definition to the original conjecture still calls for a mathematical reading of the definitions. Toledo’s November 6 report

November 5, 2026 · A preprint offers two routes to a circuit lower bound

Nikolai Chukhin, Karthik Gajulapalli, Alexander Golovnev and Ivan Mihajlin report a result that guarantees at least one of two outcomes. One is a near-maximal Boolean circuit lower bound for a problem in NE, a nondeterministic exponential-time class. The other is a separation in a constant-free model of arithmetic circuits. The proof gives the disjunction, and neither outcome on its own settles the Clay problem. The authors describe how they used GPT-6 Astra and Claude Opus 5.5 in their work. Preprint, including the authors’ AI-use account

November 3, 2026 · An explicit Boolean circuit lower bound improves

Om Swostik Mishra and Rahul Santhanam reported that an explicit Boolean function in P requires circuits of at least 4n − O(log n) gates over the full basis of two-input Boolean gates. The revised bound improves the leading constant. It still grows linearly with the number of input bits. The function itself belongs to P, so it has polynomial-size circuits. ECCC revision

October 31, 2026 · An outside reader reports successful Lean replays

Totó Busnello published logs from separate runs of both labs’ proof-checking configurations. Lean’s default kernel accepted the OpenAI proof for the formal statement named in its challenge. The Anthropic replay passed checks from both Lean’s kernel and nanoda, a second implementation. The runs checked the formal targets. Busnello identified matching those targets to the papers as work still to do. Busnello’s report on the working group’s replication thread

October 26–27, 2026 · OpenAI and Anthropic release separate ETH claims

OpenAI released its result October 26. Anthropic’s manuscript is dated October 26, and its preprint is listed October 27. Both propose deterministic subexponential algorithms that count the satisfying assignments of fixed-width Boolean formulas. A count above zero answers the 3-SAT decision question with a yes. Each project provides formal proof artifacts. In OpenAI’s case, the documented Lean theorem gives a weaker runtime bound than the revised manuscript, although both bounds are subexponential in the number of variables for fixed clause width. The public examination continues. OpenAI announcement · OpenAI’s formal scope and manuscript · Anthropic preprint · Kingy’s bound-by-bound comparison

October 6, 2026 · OpenAI releases a proposed proof of Unique Games

OpenAI’s October manuscript release included a proposed proof of the Unique Games Conjecture, which concerns the hardness of approximating a class of constraint satisfaction problems. If verified, it would establish hardness thresholds relevant to how closely efficient algorithms can approximate problems such as Max Cut, assuming P ≠ NP. In a related line of work first posted in September, Yumou Fei, Dor Minzer and Shuo Wang reported a proof about 4-to-1 games with perfect completeness. The results concern different constraints. For a November 4 talk, UT Austin’s Dana Moshkovitz outlined how she reads the proposed proof and identified a new code construction in its hardness reduction. UT Austin talk abstract · OpenAI’s manuscripts and formal scope · Fei, Minzer and Wang preprint

September 8, 2026 · OpenAI discloses an effort on the open Millennium problems

OpenAI says it began testing an internal model with coordinating agents on all open Millennium Prize Problems on September 1. That scope included P vs NP. The announcement describes how the effort concentrated on Navier–Stokes and gives no P vs NP-specific theorem, transcript or compute budget. It is a record of an effort on the direct question, weeks before the independent examination of the related SAT work. OpenAI’s account of the evaluation · Clay’s P vs NP status

What P vs NP asks

Imagine you have a list of incompatible roommate pairs and need to choose 100 people from a pool of 400 to put in one dorm. If somebody hands you a proposed list, you can check the headcount and look for incompatible pairs. Finding a valid list from scratch may require searching an enormous number of possibilities. The Clay problem asks whether every decision problem with efficiently checkable yes answers also has an efficient rule for deciding those answers. The formal definitions make “efficient” precise. Clay’s dorm example · Stephen Cook’s official problem statement

P is the class of yes-or-no problems a deterministic algorithm can solve in polynomial time in the input’s bit length in the worst case. NP is the class of yes-or-no problems whose yes instances have polynomial-length certificates that a deterministic algorithm can verify in polynomial time. NP stands for nondeterministic polynomial time. Every problem in P is already in NP. The open question is whether any problem in NP lies outside P. Cook’s definitions

In Boolean satisfiability, or SAT, the input is a logical formula, and the question is whether any assignment of true and false makes the whole formula true. For (A OR B) AND (NOT A OR C), the assignment A = true, C = true works for either value of B. A solver faces formulas of arbitrary size, including formulas for which no assignment works. In 3-SAT, each clause has at most three literals. Both SAT and 3-SAT are NP-complete. In particular, every problem in NP can be translated into a SAT or 3-SAT instance in polynomial time while preserving the yes-or-no answer. Cook’s statement and discussion of NP-completeness · Karp’s reductions

What would settle it?

  • P = NP. Prove that an NP-complete problem has a deterministic algorithm that is correct for every input and runs in worst-case polynomial time in its encoded length. A proof of existence would suffice. An explicit algorithm with a useful runtime would have additional consequences.
  • P ≠ NP. Prove that some problem in NP has no deterministic polynomial-time algorithm. For SAT, that means ruling out every polynomial-time solver, including methods nobody has invented yet. An unconditional superpolynomial size lower bound on unrestricted Boolean circuits for a single problem in NP would also suffice, because every problem in P has polynomial-size Boolean circuits.

The two outcomes concern whole classes of problems. An algorithm can win every instance in a benchmark and still have a bad worst case. A lower bound for one algorithm can be correct even when a different algorithm solves the problem quickly. Cook’s problem statement

Why the SAT claims matter

Checking assignments one at a time for a formula with n variables can take up to 2n checks. ETH says 3-SAT retains a positive exponential rate in n even with a better exact algorithm. The October manuscripts claim a bound of 2o(n) times input-size overhead for fixed clause widths. The notation means the exponent grows more slowly than n, in the precise sense that the ratio tends to zero. That is enough to contradict ETH if the claim is correct. P vs NP asks whether the runtime can be bounded by a fixed power of the input length. Impagliazzo and Paturi’s ETH paper · OpenAI announcement · Anthropic preprint

Log-scale graph of n cubed, two to the square root of n, and two to the n. The subexponential curve overtakes n cubed as n grows.

The chart compares n3, 2√n and 2n on a logarithmic scale. The curves are mathematical examples. The subexponential example eventually grows faster than every fixed power of n. It can still lie below a polynomial at smaller input sizes. The relative cost of real algorithms also depends on constants, input structure and how much work each step does. Kingy plotted the three formulas directly. Clay’s formal definition of polynomial time

A subexponential algorithm for 3-SAT also needs careful handling when it travels through a reduction. A polynomial-time reduction can expand an input of size N into a formula whose variable count is a larger power of N. A runtime subexponential in that larger count may fail to give a subexponential runtime in the original input size. Researchers therefore have to revisit which ETH-based lower bounds depend on the conjecture and which reductions preserve the relevant parameters. Polynomial time, by comparison, survives ordinary polynomial-time reductions. Impagliazzo, Paturi and Zane on reductions that preserve exponential complexity · Stearns–Hunt follow-up

How the search got here

  • 1971–73 · One problem stands in for many. Stephen Cook’s 1971 work and Leonid Levin’s independent work established the foundation of NP-completeness. Richard Karp’s 1972 paper showed how widely the idea applied, giving 21 complete problems across logic, graphs and combinatorics. This is why researchers can pursue P vs NP through a single problem such as SAT. Cook’s historical account · Karp’s 1972 paper
  • 1975 · Relativization puts a limit on black-box arguments. Theodore Baker, John Gill and Robert Solovay constructed two different oracles, or sources of answers that both sides may query. With one oracle the corresponding P and NP are equal. With the other they differ. A proof that works uniformly with every oracle can therefore settle neither outcome. Baker, Gill and Solovay’s paper
  • 1979 · Proof length becomes a research problem. Cook and Robert Reckhow formalized what makes a propositional proof system efficient. If NP equals coNP, some system gives every propositional tautology a polynomial-size certificate. A lower bound for a single system rules out short proofs only in that system. The broader question asks whether any such efficiently verifiable system can always provide short certificates. Cook and Reckhow’s paper
  • 1990s · Natural proofs expose a trade-off. Alexander Razborov and Steven Rudich identified conditions shared by a family of circuit lower-bound arguments. Assuming sufficiently strong pseudorandom functions exist, arguments satisfying their conditions cannot prove the desired general circuit lower bounds. A property that is common and easy to test among Boolean truth tables can be too useful a distinguisher for such pseudorandomness to survive. Razborov and Rudich’s paper
  • 2000 · Clay makes it a Millennium Prize Problem. The prize put a public marker on a question whose technical statement was already decades old. Clay designated $1 million per problem and published a formal description by Cook. Clay’s problem page · The Millennium Prize Problems monograph
  • 2008 · Algebrization refines the obstacle. Some methods had escaped relativization by translating Boolean computations into algebra. Scott Aaronson and Avi Wigderson showed that a broader class of arguments still fails to resolve P vs NP when the proof also works with certain algebraic extensions of the oracle. This rules out a mode of argument and leaves room for algebraic methods that escape the conditions. Aaronson and Wigderson’s paper
  • 2010 · A direct P ≠ NP claim faces public scrutiny. Vinay Deolalikar circulated a proposed proof involving finite model theory and random SAT. Researchers used public discussion threads to isolate gaps and ask which steps would survive revisions. The claim never became an accepted resolution. The episode shows the value of an inspectable argument and detailed specialist criticism. Contemporaneous technical discussion
  • 2011 · Faster algorithms help prove a lower bound. Ryan Williams showed that NEXP, the class of problems decidable in nondeterministic exponential time, has no polynomial-size ACC circuits. ACC restricts circuit depth and the types of gates allowed. The proof uses a faster satisfiability algorithm for those circuits to derive a contradiction from the assumption that they can compute all of NEXP. This established a route from algorithm design to lower bounds. Williams’s paper
  • 2025 · Researchers improve a different limit on computation. Williams gave a square-root-scale space simulation for time-bounded multitape Turing machines, building on a tree-evaluation algorithm by James Cook and Ian Mertz. It changes how researchers understand the trade-off between time and memory. The same paper also examines consequences for separations between time and space classes. Williams’s simulation paper

Where another advance could come from

Better exact SAT algorithms

A new algorithm can remove a conjectured barrier before it comes close to polynomial time. Watch for improvements in the exponent, the size of formulas the method handles, and what happens to the clause count and variable count in a reduction. A credible result says exactly what resources it uses, which inputs it covers and where its bound comes from. The 2026 counting claims matter because a single exact count can answer the associated decision problem. Anthropic’s theorem and model · Community examination

Lower bounds for stronger models

A Boolean circuit computes an answer with a network of fixed gates. The circuit lower-bound approach asks how many gates are required as inputs grow. Proving a bound for one gate basis, depth limit or uniformity condition can be substantial progress. To understand its reach, ask which problem the bound applies to, how the circuit model is restricted and whether the bound is linear, polynomial or superpolynomial. A time–space trade-off gives a different kind of result by ruling out an algorithm that is simultaneously very fast and very economical with memory. Williams on ACC circuits · Mishra and Santhanam on general two-input gates · Mudigonda and Williams on SAT time–space lower bounds

The November 5 paper by Chukhin and colleagues gives a fresh example of the connection. They note that, if OpenAI’s proposed runtime bound for sparse 3-SAT holds, known reductions yield a circuit lower bound of order n√log n at infinitely many input lengths for a problem in ENP, an exponential-time class with access to an NP oracle. That would be superlinear. The unrestricted circuit route to P ≠ NP calls for a superpolynomial bound for a problem in NP. Chukhin and colleagues on the circuit consequence

Proof complexity and hardness of approximation

Proof complexity asks how much evidence a system needs to establish, for example, that a formula is unsatisfiable. Hardness of approximation asks whether an algorithm can get within a specified gap of an optimum. Each research program can tighten a different limit. A proof lower bound has to name its proof system. An approximation result has to name the gap, the problem and the complexity assumptions behind the guarantee. Unique Games belongs to the latter line of work. Cook and Reckhow on proof systems · Fei, Minzer and Wang on games hardness

What the answer would change

A practical algorithm establishing P = NP would make exact solutions accessible for many search and optimization problems now handled by special-purpose methods. A SAT decision solver can recover a satisfying assignment by fixing one variable at a time and asking whether the restricted formula still has a solution. A large exponent or constant could make a polynomial-time algorithm unusable at ordinary sizes. A proof of P ≠ NP would establish worst-case limits while leaving room for solvers that work well on structured instances. Cook’s discussion of consequences

Cryptography raises an additional question about which instances are hard. If P = NP, efficient verification could be turned into efficient search in the asymptotic sense, ruling out standard one-way functions. The practical consequences for a particular system would depend on how expensive the resulting algorithm is. If P ≠ NP, the existence of hard worst cases would still leave open whether appropriate inputs are hard often enough to support cryptography. Cook on one-way functions and cryptography

How to evaluate the next proof claim

  1. Read the exact theorem. Check the input parameter, computational model and hypotheses. A theorem about bounded-width SAT, a restricted circuit family or an approximation gap has a scope of its own.
  2. Read the proof and the formal statement. A Lean kernel can check a formal argument from declared assumptions. Compare the formal statement with the paper and Clay’s problem. Check the imported assumptions and which bound the formalization covers.
  3. Look for independent technical examination. A public preprint makes a claim inspectable. A formal build makes specific mechanical checks possible. Expert scrutiny can test the interpretation of the statement, the reductions and unresolved objections.
  4. Follow prize recognition separately. Clay’s rules require publication in a qualifying outlet, a wait of at least two years after publication, and general acceptance in the global mathematics community before it will consider a proposed solution.

These distinctions apply whether a proof comes from a mathematician, an AI system or a collaboration. For the current ETH claims, the public working group offers a place to follow changes in the arguments, outside checks and the consequences for other problems. Lean’s proof validation guidance · ETH discussion and examination · Clay prize rules

Sources to follow