Tractable versus Intractable
Tractable problems have efficient (polynomial-time) algorithms; intractable ones require time that explodes with input size.
The working definition
A problem is tractable if it has a polynomial-time algorithm, placing it in P. It is intractable if no such algorithm exists (or is known and believed not to). The polynomial/exponential boundary is the standard, if imperfect, line between feasible and infeasible.
Why polynomial is the cutoff
Polynomial growth stays manageable as inputs scale; doubling the input multiplies the work by a constant factor. Exponential growth does not: adding one element can double the work, so even inputs of a few dozen elements can exceed any conceivable computer's capacity.
A vivid contrast
- O(n^2) on n = 1,000,000: about 10^12 steps, hard but doable
- O(2^n) on n = 60: about 10^18 steps, beyond practical reach
- O(2^n) on n = 300: more steps than atoms in the observable universe
Known versus believed intractable
Some problems are provably intractable, requiring exponential time no matter the algorithm. Others, like NP-complete problems, are only believed intractable: no efficient algorithm is known, but none has been proven impossible. That distinction rests on the open P vs NP question.
The polynomial caveat
The cutoff is a useful convention, not a law of nature. An O(n^100) algorithm is technically tractable but useless, while a 1.001^n algorithm is technically intractable but fine for small n. In practice most tractable problems have low exponents and most intractable ones truly blow up, so the heuristic holds well.
What to do with intractable problems
Intractability is a redirection, not a dead end. Options include solving special cases that lie in P, using approximation algorithms with quality guarantees, applying heuristics that work on typical inputs, or accepting exponential solvers when inputs stay small.