Tractability Boundaries¶

Understanding the boundary between tractable (polynomial) and intractable (exponential) problems guides whether to seek exact solutions, approximations, or heuristics, and prevents wasted effort on provably hard problems.

Tension Addressed¶

Exact vs. Approximate Solutions (defines when exact is impractical)

Recognizable As¶

"This problem is NP-hard," recognizing traveling salesman variants, satisfiability at the core of constraint systems, approximation algorithms with provable bounds

Canonical Sources¶

Cook, The Complexity of Theorem Proving Procedures (1971); Karp, Reducibility Among Combinatorial Problems (1972); Garey and Johnson, Computers and Intractability (1979)

Transfers To¶

Cryptographic security assumptions, operations research, logistics optimization, machine learning (computational learning theory), resource scheduling

Recognizing intractability is as valuable as solving problems: it redirects effort toward approximation, heuristics, or problem reformulation.