You already know from that some algorithms scale gracefully and others fall off a cliff. This page zooms out from a single algorithm to a whole problem and asks a bigger question: is there any reasonably fast algorithm for it at all? For some problems the answer is a confident "yes"; for others, despite decades of the sharpest minds trying, the only methods we know amount to little more than trying everything — and that gets hopeless with terrifying speed.

That split has a name. A problem is tractable if we have an algorithm that solves it in polynomial time; it is intractable if every algorithm we know takes exponential time. In this one page you'll learn exactly where that line falls and why it matters, meet the two famous classes P and NP, see why a Sudoku is fiendish to solve but trivial to check, and meet the most famous unanswered question in all of computer science: does P = NP?

The dividing line: polynomial vs exponential

The dividing line between tractable and intractable is drawn at polynomial time. An algorithm runs in polynomial time if its worst-case step count is bounded by n raised to some fixed power — O(n), O(n^2), O(n^3), even O(n^{100}) — where n is the size of the input. These are the growth classes that keep up as inputs get big.

• Tractable — solvable in polynomial time. Feasible in practice, even for large n. Sorting a list (O(n \log n)), searching (O(\log n)), finding the shortest route on a map (O(n^2)) — all tractable.
• Intractable — the only known algorithms take exponential time, like O(2^n) or worse (O(n!)). The work explodes so fast that even a modest input is already out of reach of every computer on Earth combined.

Why draw the line exactly there? Because polynomials behave themselves and exponentials do not. Double the input to a polynomial algorithm and the work grows by a fixed factor (O(n^2) work goes up fourfold — annoying, but survivable). Add just one to the input of an O(2^n) algorithm and the work doubles. A faster computer barely helps: buy a machine a thousand times faster and you can handle an input just ten items larger, because 2^{10} \approx 1000. That is the practical meaning of "intractable" — not "slow", but uncatchable.

See why exponential is a different beast

The chart plots the number of steps against the input size n for a couple of polynomial curves (n and n^2) against the exponential 2^n. Watch what happens: for tiny n on the left the exponential is actually the lowest line — it looks harmless. But it curls upward and, within a handful of steps, rockets clean off the top of the frame, leaving even n^2 looking flat by comparison.

That crossover is the whole story. The polynomial curves are the ones we can live with; the exponential is the one that dooms us. To feel just how violent the gap becomes, look at the actual step counts — imagine each step takes a billionth of a second (a fast modern computer):

The n^2 column stays comically small the whole way down. The 2^n column starts small, then annihilates any hope of finishing. An intractable problem with an input of a hundred items isn't "hard" — it is, for exact answers, permanently out of reach.

P: the problems we can solve quickly

Computer scientists gather all the tractable decision problems into one big club called P — for Polynomial time. A problem is in P if there exists an algorithm that solves it from scratch in polynomial time. If you can name a real algorithm whose worst case is O(n^k) for some fixed power k, the problem is safely inside P.

Loads of everyday problems live here: sorting a list, searching it, finding the shortest path between two towns, checking whether a number is prime, multiplying two matrices. These are the problems we happily throw at a computer and expect an answer back before we've finished our tea. P is, roughly, "the problems computers are actually good at."

NP: the problems we can check quickly

Now here is the subtle, beautiful idea. Forget solving for a moment and think about checking. Suppose someone hands you a proposed answer — a filled-in Sudoku grid, a complete timetable, a suggested route — and simply claims "here, this works." How long does it take you to verify their claim?

NP — Nondeterministic Polynomial time — is the class of problems whose proposed solutions can be checked in polynomial time, even if finding one from scratch might be brutally hard. The magic word is a certificate: a candidate answer that, if correct, lets you confirm "yes" quickly.

• Filled-in Sudoku: handed a completed grid, you just scan every row, column and box for duplicates. A quick, polynomial check — even though finding that grid may have taken serious effort.
• Timetabling: handed a full school timetable, you sweep through checking no teacher or room is double-booked and every class is placed. Fast to check; agonising to build.
• Jigsaw / a locked padlock: a scrambled jigsaw is slow to solve but obvious to check once assembled; a 4-digit combination is a pain to crack but instant to verify once you're told it.

Notice something important: every problem in P is also in NP. If you can solve a problem quickly, you can certainly check an answer quickly — just solve it yourself and compare. So P sits inside NP. The interesting problems are the ones in NP that we don't (yet) know how to fit into P: easy to check, seemingly hard to solve.

The classic example: hard to solve, easy to check

Sudoku on the ordinary 9 \times 9 grid is a gentle puzzle, but generalise it to an n^2 \times n^2 grid and it becomes a genuine NP problem, and it perfectly captures the asymmetry at the heart of this page:

• Solving a large blank-ish grid may need you to explore an astronomical number of combinations — the search space explodes exponentially. Hard.
• Checking a completed grid is a quick sweep for repeats. Easy.

The little program below makes that concrete. checkSolution verifies a small completed grid in a handful of passes — a polynomial-time check. Contrast that with the effort it would take to discover that grid from a nearly empty one. Press Run.

That gulf — trivial to check, punishing to solve — is exactly what puts a problem in NP but leaves us unsure whether it belongs in P. Which brings us to the million-dollar question.

The famous open question: does P = NP?

We know P is a part of NP. The staggering unknown is whether they are actually the same club. Restated in plain words:

Almost everyone believes P \neq NP — that some problems really are fundamentally harder to solve than to check — but believing is not proving. If someone ever showed P = NP with a practical algorithm, the consequences would be earth-shaking: every quick-to-check problem (protein folding, optimal timetables, countless logistics puzzles) would suddenly become quick-to-solve. And, as we'll see, a great deal of the security we rely on every day would collapse.

Living with intractability: heuristics and approximations

If a problem is intractable, we can't just give up — real businesses still need delivery routes and timetables. So instead of demanding a perfect answer in exponential time, we settle for a good-enough answer in polynomial time. Two everyday tools:

• Heuristics — clever rules of thumb that usually find a decent answer fast, with no guarantee it's the best. A sat-nav planning a delivery round might use "always visit the nearest unvisited stop next" — quick, sensible, occasionally a bit wonky.
• Approximation algorithms — methods that run in polynomial time and come with a provable promise, e.g. "never worse than 1.5× the optimal route." You trade a guarantee of perfection for a guarantee of speed plus closeness.

The travelling salesman problem — find the shortest round-trip visiting every city once — is the poster child. Solving it exactly is intractable, so no courier company on Earth does that. They run heuristics and approximations and cheerfully accept a route that's within a whisker of optimal but computed before lunch. Good-enough-and-fast beats perfect-but-never.

Why cryptographers love hard problems

Here's a delicious twist: intractability isn't only a nuisance — sometimes it's exactly what we want. Much of modern cryptography is deliberately built on problems that are easy one way and believed-to-be-hard the other.

The classic case is factoring. Multiplying two big prime numbers together is easy (polynomial). But taking the huge result and recovering the two primes — factoring it back — is believed to be intractable for classical computers. RSA, one of the workhorses of internet security, hides its secret behind exactly this asymmetry: your browser can lock a message with the product, but an eavesdropper would need to factor an enormous number to unlock it, which would take longer than the universe has left. The hardness is the lock. This is also why a proof that P = NP would be a security catastrophe: it would suggest these "one-way" doors might swing open both ways after all.