Theory of Computation & Computer Graphics — Turing Machine, NEC licence examination syllabus (Nepal Engineering Council).
Intractability: problems that are technically solvable, but hopelessly slow
"Solvable in theory" and "solvable before the universe ends" are very different claims.
tractable ≈ n³ steps · intractable ≈ 2ⁿ steps With n = 20, poly = 8000, exp = 1048576.
At n = 20 the exponential is already ahead. At n = 60 it is beyond anything that could ever be computed, while n³ is still only 216,000 steps.
An intractable problem is one for which no known algorithm runs in polynomial time — the best known solutions take exponential (or worse) time, meaning even modestly larger inputs quickly become impossible to solve in any practical amount of time, even on the fastest hardware imaginable.
Why exponential growth is brutal:
A problem taking 2ⁿ steps: n=20 → about 1 million steps (instant)
n=50 → about 1 quadrillion steps (days)
n=100 → more steps than atoms in the universe
This is exactly why NP-Complete problems are considered intractable
at any meaningfully large input size.
💡 One-liner: "Why are NP-Complete problems considered intractable in practice, even though they're technically 'solvable'?" → Their best known algorithms take exponential time, which becomes computationally hopeless for even moderately large inputs.
What "intractable" costs, in actual numbers
The word means "solvable in principle but not in practice", which sounds like a matter of degree. It is not. Put numbers on it and the gap is absolute.
Comparing n³ against 2ⁿ:
n = 10 n³ = 1,000 2ⁿ = 1,024 (comparable)
n = 20 n³ = 8,000 2ⁿ = 1,048,576 (2ⁿ pulling ahead)
n = 50 n³ = 125,000 2ⁿ ≈ 1.1 × 10¹⁵ (hopeless already)
n = 100 n³ = 1,000,000 2ⁿ ≈ 1.3 × 10³⁰
At a billion operations per second, 2¹⁰⁰ steps takes about 4 × 10¹³ years — roughly 2,900 times the age of the universe. Meanwhile n³ at the same input size is a million operations, finishing in a millisecond. Same input, same computer.
💡 Note how ordinary n = 100 is. This is not an exotic input size — it is a small graph, a short list, a modest puzzle. Exponential algorithms fail on inputs that look trivially small, which is what makes intractability a practical concern rather than a theoretical one.
Why a faster computer does not help
The instinctive response is that hardware will catch up. It cannot, and the reason is worth being precise about.
Each additional unit of input doubles the work for a 2ⁿ algorithm. So a computer a thousand times faster does not handle a thousand times larger input — it handles about ten more units of input, since 2¹⁰ ≈ 1000. Another thousandfold speedup buys ten more. Hardware improvements add a constant to the manageable input size, while the problem multiplies.
💡 A polynomial algorithm behaves entirely differently: a thousandfold speedup lets an n³ algorithm handle a ten times larger input, because 10³ = 1000. Speed multiplies what polynomial algorithms can do and merely adds to what exponential ones can do — which is the real content of the tractable/intractable distinction.
What is done instead
Intractable problems still have to be solved in practice, so the answer is to give something up: accept an approximate answer rather than an optimal one, use a heuristic that is usually fast without a guarantee, solve only the special cases that actually arise, or accept exponential time on the small inputs where it is affordable.
Syllabus points
Intractable problems
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.