Time Complexity & the Class P

a tractable problem

Tractable is the word complexity theory uses for a problem we can actually solve at scale, as opposed to one whose solution slips out of reach as the input grows. The intuition is the one from everyday life: a chore is tractable if doing it on twice the work takes a sensibly bounded amount more effort, not an explosion of it. By long-standing convention, we make tractable precise by identifying it with membership in P: a problem is tractable if it has a polynomial-time algorithm.

Why pick P as the official meaning? Because it draws the line exactly at the canyon in the growth-rate ladder, between polynomial and exponential. A polynomial-time algorithm responds gracefully to bigger inputs and to faster hardware, while an exponential one is defeated by both. Equating tractable with P also gives the word the same robustness P enjoys: because all reasonable deterministic models simulate each other with polynomial overhead, tractability is a property of the problem, not of the programming language or the particular computer. So sorting, shortest paths, matching, and primality are tractable; the brute-force versions of SAT or the travelling salesman tour are not (and may be inherently intractable, though that is unproven).

The identification is a useful idealisation, not gospel, and it is worth saying so plainly. On the optimistic side, a problem can be 'intractable' in the worst case yet be solved routinely in practice by heuristics or because real inputs are easy. On the pessimistic side, a problem can be 'tractable' (in P) yet have an algorithm so slow, with an exponent like n^100 or a monstrous constant, that no one can run it. Tractable equals polynomial-time is the right default and the right teaching line, as long as you remember it is a stand-in for feasibility, not a guarantee of it.

Maximum matching (pair up as many people as possible given who is compatible) is tractable: it has a polynomial-time algorithm, so even with thousands of people we get an exact answer quickly. Finding the shortest travelling-salesman tour over those same people is not known to be tractable; the obvious method tries n! orderings and chokes around n = 20.

Matching is tractable (in P); the travelling-salesman tour is not known to be.

'Tractable = in P' is an idealisation: a worst-case-intractable problem may be easy in practice, and an n^100 algorithm is in P yet unusable; treat the identification as the standard convention, not a literal guarantee.

Also called
feasible problemefficiently solvable problemproblem in P易解問題可行問題