Time Complexity & the Class P

intractability

There is a world of difference between a problem that takes a computer a few seconds longer when the input grows and one whose running time explodes so fast that even modest inputs are out of reach forever. We call the second kind intractable: not impossible in the logical sense (an answer exists and an algorithm can find it given unlimited time), but hopeless in practice because the time required grows exponentially or worse with the input size. The brute-force search that tries all 2^n subsets of n items is the picture to keep in mind.

Why is exponential growth so deadly? Because each extra unit of input multiplies the work instead of adding to it. Suppose a 2^n step algorithm handles n = 50 in a day. Then n = 60 takes 2^10 = 1024 days, nearly three years; n = 70 takes about three thousand years; n = 80 outlives civilisations. Worse, faster hardware barely helps: a computer a million times faster only lets you handle about 20 more elements, because a million is roughly 2^20. Contrast a polynomial method, where doubling the input multiplies the time by a fixed factor, and a faster machine multiplies the input you can handle. That asymmetry is precisely why the polynomial-versus-exponential line is the line between tractable and intractable.

Be careful with the word, though, in two directions. First, intractable here means 'not solvable in polynomial time as far as we can do it', and for many famous problems (the NP-complete ones) we do not actually have a proof that no polynomial algorithm exists; we only strongly suspect it because P versus NP is open. Second, undecidable is a stronger and different verdict: the halting problem has no algorithm at all, at any cost, whereas an intractable problem does have an algorithm, just an impractically slow one. Intractable means slow beyond use; undecidable means no method exists.

Trying to crack a password by checking every string of length n over a 26-letter alphabet means 26^n tries: 26^6 is about 300 million (seconds on a fast machine) but 26^12 is about 9 times 10^16 (decades). Each extra character multiplies the work by 26, the signature of intractability, while a polynomial-time check of a single guess is instant.

Exponential growth multiplies the work per extra input unit, so even fast hardware adds only a tiny handful of feasible elements.

'Intractable' means an algorithm exists but is impractically slow (exponential); it is NOT the same as 'undecidable', where no algorithm exists at all. For NP-complete problems, intractability is strongly suspected but unproven (P vs NP is open).

Also called
intractable probleminfeasible in practiceexponential blowup of running time難解問題