P vs NP Explained Simply: Is It Solved in 2026?

Quick answer: P vs NP asks whether every problem whose solution can be checked quickly can also be solved quickly. P is the class of problems solvable in polynomial time; NP is the class whose solutions can be verified in polynomial time. It is one of the seven Millennium Prize Problems, worth 1 million dollars, and it is still unsolved. In October 2026, OpenAI and Anthropic each claimed AI-found refutations of the Exponential Time Hypothesis, a stronger assumption; P vs NP itself is unaffected.

Solving a hard Sudoku can take an hour. Checking someone else’s finished grid takes a minute. Is that gap real, or just a sign we have not found a clever enough method? That, in essence, is the P vs NP problem, the most famous open question in computer science.

P and NP in Plain Words

ClassMeaningExample
PCan be solved in polynomial time (steps grow like \(n^k\))“Is there a route from A to B of length at most 100 km?” on a road map with nonnegative distances
NPFor “yes” answers, a short certificate (a proposed solution) can be checked in polynomial timeGeneralized Sudoku (grids that can grow), 3-SAT, “can these exams fit in k time slots?”
NP-completeProblems in NP to which every NP problem reduces in polynomial time: solve one fast and you solve all of NP fast3-SAT, traveling salesperson (decision version), generalized Sudoku

Every problem in P is in NP: if you can solve it fast, you can check an answer fast by solving it again. The question is whether the reverse holds: does \(P = NP\)?

Why Polynomial Time?

Compare \(n^2\) with \(2^n\) as \(n\) grows:

\(n\)\(n^2\)\(2^n\)
101001,024
30900about 1.07 billion
10010,000about \(1.27 \times 10^{30}\)

Trying every possibility often takes exponential time. Polynomial-time algorithms stay practical as inputs grow; exponential ones quickly become hopeless. See our guide to exponential growth for more on why.

Why Is It Worth a Million Dollars?

The Clay Mathematics Institute lists P vs NP among its seven Millennium Prize Problems. Stephen Cook formalized it in 1971 (Leonid Levin found similar ideas independently). Most experts believe \(P \ne NP\). If instead \(P = NP\) with a practical algorithm, much of modern cryptography, which relies on some problems being hard, would be in trouble.

The 2026 Exponential Time Hypothesis Shock

The Exponential Time Hypothesis (ETH), introduced in the late 1990s by Russell Impagliazzo, Ramamohan Paturi and Francis Zane, says something stronger than \(P \ne NP\): that 3-SAT cannot be solved in time \(2^{o(n)}\), meaning no algorithm beats brute force by more than a constant factor in the exponent. Hundreds of results in fine-grained complexity assume ETH.

On October 26, 2026, OpenAI and Anthropic each announced AI-found algorithms that would refute ETH, solving (and counting solutions of) 3-SAT in time roughly \(2^{O(n \log\log n/\sqrt{\log n})}\), slightly subexponential. Both released Lean formalizations; OpenAI’s own scope note says its Lean development proves a slightly weaker, but still subexponential, bound than the manuscript states. Key points:

  • P vs NP is not settled. Proving \(P = NP\) needs a polynomial-time algorithm for an NP-complete problem. A subexponential algorithm can still be slower than every polynomial. Separately, reductions between problems can enlarge inputs, so the speedup does not automatically carry over to all of NP.
  • No demonstrated practical speedup. The published bounds are asymptotic, and reports suggest they only beat brute force for astronomically large inputs.
  • Independent review is continuing. Impagliazzo, Paturi and Ryan Williams wrote that their involvement should not be taken as certification. As of a November 19, 2026 UC San Diego report, examination was ongoing; reviewers have reported that the Lean code compiles, while the question of whether the formal statements match the papers is still being checked.

Common Misconceptions

“NP means not polynomial.” No. It stands for nondeterministic polynomial time: answers can be checked quickly.

“AI just solved P vs NP.” No. The 2026 claims concern ETH, a stronger assumption. P vs NP remains open.

Watch: P vs NP in Video

If you learn better by watching, these videos are worth your time.

P vs NP Explained: Computer Science’s Biggest Puzzle (Quanta Magazine). A clear animated introduction.
P vs. NP – The Biggest Unsolved Problem in Computer Science (Up and Atom). A friendly explanation with everyday examples.
MIT Professor: What is Strong ETH (Ryan Peterman). An MIT professor on ETH and its strong version, recorded after the 2026 claims.

Check Your Understanding

Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.

Answer each question and press Submit to see your result right away.

1. What does NP stand for?
Found a bug? Let us know!
2. Which is true?
Found a bug? Let us know!
3. About how big is 2 to the 30?
Found a bug? Let us know!
4. What did the October 2026 AI claims refute?
Found a bug? Let us know!
5. If P = NP with a fast algorithm, what would be most at risk?
Found a bug? Let us know!

Frequently Asked Questions

What is P vs NP in simple terms?

It asks whether every problem whose solution can be checked quickly can also be solved quickly. P problems can be solved quickly; NP problems can be checked quickly.

Has P vs NP been solved?

No. As of November 2026 it is still open and still one of the Clay Institute’s million-dollar Millennium Prize Problems. The 2026 ETH claims give subexponential, not polynomial, algorithms, so they do not settle it.

What is the Exponential Time Hypothesis?

ETH, proposed by Impagliazzo and Paturi, says 3-SAT cannot be solved in subexponential time 2^{o(n)}. It is stronger than P not equal to NP. In October 2026, OpenAI and Anthropic each claimed AI-found refutations, still under expert review.

Did AI disprove P vs NP?

No. The 2026 AI results concern ETH. Even if correct, they do not show P = NP.

Keep Exploring

Sources and Further Reading

Related to This Article

What people say about "P vs NP Explained Simply: Is It Solved in 2026? - Effortless Math"?

No one replied yet.

Leave a Reply