tractable

Tractable is an adjective meaning manageable or solvable with reasonable effort, cost, or resources. In everyday use it describes problems, processes, or datasets that can be effectively handled. The term derives from Latin tractabilis, meaning "able to be drawn or managed," from tractare, to handle or treat.

In mathematics and computer science, tractability refers to the existence of algorithms that solve a problem efficiently. A common formal notion is polynomial-time solvability: a problem is tractable if it can be solved in time that is a polynomial function of the input size on a deterministic Turing machine. Problems that require super-polynomial time are typically described as intractable. The boundary between tractable and intractable is central to complexity theory; many problems are intractable in general, but become tractable for restricted input classes or with fixed parameters (fixed-parameter tractability, FPT).

In optimization and operations research, tractable problems are those for which efficient algorithms exist. Classic examples include linear programming and convex optimization, which can be solved in polynomial time. Many combinatorial problems are intractable in full generality (for example, the traveling salesman problem), but practical instances can be solved quickly or approximated via relaxations, heuristics, or specialized structures.

In probabilistic reasoning and statistics, tractable models permit exact inference; for example, tree-structured graphical models allow polynomial-time exact computation of marginal probabilities. More complex models may require approximate inference methods such as Monte Carlo or variational techniques, reflecting practical intractability of exact solutions.

Usage of the term often contrasts with intractable or difficult, and emphasizes solvability, efficiency, or feasibility in algorithms, inference, or optimization.