intractability

Intractability refers to the property of a problem that makes finding an exact solution computationally difficult to the extent that no efficient algorithm is known or believed to exist. In computer science, tractability is typically measured by time complexity; problems solvable in polynomial time are considered tractable, while those requiring super-polynomial time are often described as intractable. The term is most often used in the context of worst-case analysis.

In complexity theory, many intractable problems are classified as NP-hard or undecidable. NP-hard problems include optimization or decision problems for which no polynomial-time algorithm is known, unless P=NP. Undecidable problems have no algorithm that solves all instances, regardless of time.

Classic examples include the traveling salesman problem (optimization), which is NP-hard; SAT, the boolean satisfiability problem, which is NP-complete; the graph coloring problem for three or more colors, which is NP-complete; and the halting problem, which is undecidable.

In practice, intractability motivates the use of approximate and heuristic methods, probabilistic algorithms, and restrictions to special cases or parameterized versions. Approximation algorithms aim for near-optimal solutions, while heuristics prioritize speed over guarantees. Fixed-parameter tractability studies how some parameters influence complexity, enabling efficient solutions for small parameter values.

An intractable problem is not inherently unsolvable; it is often solvable for many real-world instances or under additional structure. The term can reflect theoretical limits rather than everyday practicality.