Tractability

Tractability is the line complexity theorists draw between problems that can be solved in practice and those that cannot, once the inputs get large. A problem is considered tractable, or feasibly solvable, when there is an algorithm whose running time grows only polynomially with the input size, that is, time in O(n^k) for some fixed exponent k. Problems that require exponential time are considered intractable, because the work explodes so fast that even modest inputs become hopeless.

The Stanford Encyclopedia of Philosophy entry on computational complexity frames this through the Cobham-Edmonds thesis, which equates feasible computation with polynomial-time computation: a problem is feasibly decidable just in case it lies in the class P. By the same account, a sufficient condition for a decidable problem to be intractable is that its most efficient algorithm has at best exponential time complexity.

The choice of polynomial time as the boundary is a useful idealization rather than a sharp physical law. An algorithm that runs in time proportional to n raised to a huge power would not be practical, and some exponential-time algorithms work fine on the inputs that actually arise. Still, the polynomial-versus-exponential split has proven remarkably durable as a first cut at what is and is not achievable.

This is exactly why NP-hardness matters. When a problem such as the traveling salesman problem is NP-complete, the best known methods amount to searching an exponentially large space of candidate solutions, which places it on the intractable side of the line unless the open P versus NP question is someday resolved in favor of P. Tractability is the practical stake behind that famous theoretical puzzle.

Sources

Last verified June 8, 2026