Why I wrote this

I watched a video about AI and "NP problems" and understood almost none of it. I've been a backend developer for years and had never heard of P vs NP. So I went back to zero and learned it one small step at a time. The deepest parts (how one problem is turned into another) still lost me, so this covers only what I actually understood. It's written for anyone starting where I started.

Step 1: How fast is "fast"?

Everything here depends on one idea: how the work grows when the input grows. Take n = 1,000 items:

Growth Steps Feels like
n 1,000 instant
n² 1,000,000 instant
n³ 1,000,000,000 about a second
2ⁿ a number with 302 digits never finishes

The first three are polynomial: n multiplied by itself a fixed number of times. The last is exponential: every extra item doubles the work.

Step 2: P, problems we can solve fast

P is the group of yes/no problems a computer can solve in polynomial time. You use them every day:

  • Sorting a list (every ORDER BY)
  • Finding the shortest route on a map
  • Comparing two files (git diff)
  • Checking whether a number is prime (proven to be in P only in 2002)

P is not a tool. It's a label that says "a fast, exact method exists for this."

Step 3: NP, problems where a YES can be checked fast

NP is the group of yes/no problems where, if the answer is YES, someone can hand you a short proof and you can check it fast.

Example, Subset Sum: does some subset of {10, 20, 30, 40, 50, 60} add up to 100?

  • Someone hands you {10, 30, 60}.
  • You check: 10 + 30 + 60 = 100. Done in two additions.

Checking is easy. Finding that subset is the hard part: 6 numbers have 64 subsets, and 60 numbers have 2⁶⁰ subsets, about 36 years of work at a billion checks a second.

Two common mix-ups:

  • NP does not mean "Not Polynomial." It means "Nondeterministic Polynomial": a machine that always guessed right would solve it fast.
  • NP is lopsided. It promises a fast check for YES answers only. "Is there no subset that adds up to 100?" has no known short proof.

Step 4: The open question

Every problem in P is also in NP: if you can solve it fast, you can check it fast by just solving it. So P sits inside NP.

┌──────────── NP: a YES can be checked fast ────────────┐ │ ┌──── P: can be solved fast ────┐ │ │ │ sorting, shortest path, ... │ Subset Sum, │ │ └───────────────────────────────┘ Sudoku, ... │ └───────────────────────────────────────────────────────┘ 

P vs NP asks: is the outer box actually the same as the inner box? If an answer is easy to check, is it always easy to find? Nobody knows. Most experts believe not, but nobody has proven it, for more than 50 years.

Step 5: The hardest problems in NP

Some NP problems are special: NP-complete. Every NP problem can be translated into any one of them, quickly. So a fast method for just one of them would give a fast method for all of NP, and P would equal NP.

Familiar NP-complete problems:

  • 3-SAT: can a list of "this OR that OR the other" rules all be true at once?
  • Sudoku (on large grids)
  • Exam timetabling with 3 or more slots and clashes
  • Delivery routes: can a van visit every shop in under X km?

Strange detail: the same problems in a slightly easier form are fast. Timetabling with 2 slots is easy. With 3, it's NP-complete.

Step 6: The base of the exponent matters a lot

Exponential doesn't always mean 2ⁿ. For 3-SAT, researchers had already got the best known method down to about 1.3ⁿ. That sounds like a small change. At a billion steps a second:

Method n = 100 n = 300
2ⁿ about 40 trillion years hopeless
1.3ⁿ about 4 minutes about 10³⁴ steps, hopeless again

So 1.3ⁿ is far better than 2ⁿ, and still exponential.

Step 7: The AI news

In October 2026, OpenAI and Anthropic each said their AI had found, on 16 October, a method for 3-SAT that grows slower than cⁿ for every c > 1. The technical word is subexponential.

If it holds, it breaks the Exponential Time Hypothesis (Impagliazzo, Paturi and Zane, 1998/1999): the assumption that 3-SAT needs at least cⁿ time for some fixed c > 1. Many other results were built on that assumption, which is why theorists call it big news.

The ladder looks like this:

2ⁿ → 1.3ⁿ → subexponential (the new claim) → polynomial (= P) 

The claim moves 3-SAT one rung up. P vs NP is about the top rung.

What it does NOT mean

  • P vs NP is still unsolved. Subexponential is still far from polynomial.
  • No practical speedup. Ryan Williams, who leads the expert group checking it, told the New York Times there are no immediate practical applications.
  • No help for other NP problems. Lance Fortnow noted it gives nothing new for Subset Sum or the Traveling Salesman. Translating one problem into another makes the input bigger, and for fine differences like this, that growth eats the gain.
  • Not fully verified yet. Both labs say their proofs were machine-checked (in Lean), but as of early November no independent human review had finished.

What changed for me as a developer

Honestly: for daily backend work, I don't need most of this. What I do need is Step 1, how work grows with input. That one idea now explains things I see every week.

One example: choosing the order in which to join tables is a hard search problem. With 12 tables there are already 479,001,600 possible left-to-right orders (12!). That's why Postgres, by default, stops searching exhaustively at 12 tables (geqo_threshold) and switches to a "good enough" genetic search.

The bigger lesson for me: when a headline goes over my head, the basics are the shortcut, not the detour.

What's something you learned surprisingly late in your career?

Sources