Is tractability the same as computability?

No. A computable problem may still require impractical resources. Undecidability concerns a different limitation on general algorithmic solutions.

Does a polynomial bound settle practical performance?

No. It provides a scaling classification, which must be complemented by implementation and workload evidence.

Can an intractable general problem have tractable special cases?

Yes. Restrictions on structure or representation can materially change the complexity of the task.

AI Glossary / Graphs and symbolic AI / Intermediate

Tractability

Definition

Tractability describes whether a computational problem can be solved with manageable resources. In complexity theory, a common formal meaning is that an algorithm solves every instance in time bounded by a polynomial in the encoded input size.

What it means

The term connects two related questions: how an algorithm scales in principle, and whether a particular workload is practical on available resources. They are not identical. A high-degree polynomial can be impractical, while an exponential algorithm may handle small or specially structured cases well.

AI uses tractability when discussing search, inference, planning, optimization and learning. A representation can make a task easier or harder by changing what must be considered and which relationships are allowed.

Always identify the actual task. Finding one feasible solution, finding the best solution, counting all solutions and checking a proposed solution can have very different computational requirements. A claim about one should not be silently transferred to another.

How it works

Complexity analysis describes resource growth as a function of input length. An algorithm taking roughly n squared operations is polynomial; one exploring two to the n alternatives has exponential growth in n. The input encoding matters, especially when numbers can represent large values using relatively few bits.

To make a difficult AI problem manageable, a system may restrict its language, exploit structural properties, use approximation, accept incomplete search or work within a bounded parameter. Each option changes the guarantees or the class of instances covered.

Worst-case analysis describes the hardest instances of a size, not the time for every individual instance. Conversely, a fast demonstration does not establish a favorable worst-case bound. Useful engineering combines theoretical conditions with measurements on representative data and explicit limits on time, memory and answer quality.

Three practical examples

A planning team limits its model to a structured subclass so that a required inference procedure has a suitable complexity guarantee.
A search service uses a heuristic when exhaustive exploration would exceed its response budget, while acknowledging that optimality may be lost.
A researcher studies how a graph's width affects exact probabilistic inference instead of describing all graphs with the same variable count as equally difficult.

Think of it this way

Think of a route through a building whose number of doors grows as the building expands. Some procedures inspect each room a few times; others explore every combination of open and closed doors.

The analogy illustrates scaling, not a formal complexity proof. Real runtimes depend on representation, implementation and hardware, and a cleverly structured building may make a normally difficult search easy. A single easy layout cannot establish that all layouts are manageable.

Worked example

Comparing two growth patterns

Use a teaching model in which one algorithm performs n squared operations and another performs two to the n operations. At n = 20, the counts are 400 and 1,048,576. At n = 40, they are 1,600 and 1,099,511,627,776.

Doubling n multiplies the quadratic count by four, but multiplies the exponential count by 1,048,576. If both hypothetical operations took one microsecond, the n = 40 exponential case would take about 1,099,512 seconds, or 12.7 days. The quadratic case would take 0.0016 seconds.

These are arithmetic illustrations under an artificial equal-cost assumption. They are not benchmarks and do not show that every exponential method is slower at every size. Their purpose is to show why growth rate can dominate constant-factor improvements as inputs increase.

Illustrative case study

Fictional case: Alder Planning demonstrates an exact optimizer on ten jobs and promises the same turnaround for several thousand. A reviewer asks which part of the algorithm grows with job count and whether the demonstration has the same constraints as the intended workload.

The team discovers that a search shortcut relies on a special ordering property absent from some customer cases. It separates the supported subclass from the general problem, measures memory as well as runtime, and defines what happens when the exact solver reaches its limit.

For larger cases it evaluates an approximate alternative against clear quality criteria. The report distinguishes proven guarantees from observed performance. No universal speedup or optimality claim follows from the fictional project.

Common misconceptions and mistakes

Polynomial time always means fast enough. Exponents, constants and memory requirements can still make a method impractical.
NP-hard means every instance is impossible to solve. It describes a general complexity relationship; many instances may be manageable.
A fast heuristic proves a problem is tractable. A heuristic without the required correctness guarantee does not establish a polynomial-time solution to the exact general task.

Business use

Tractability is useful for deciding which promises an AI system can responsibly make at the intended scale. It encourages teams to ask how workload growth changes cost and which assumptions support the chosen method.

Ask vendors or researchers to specify input size, resource measure, exact or approximate output, and the conditions under which their guarantee holds. Include difficult but realistic cases in evaluation. A bounded response policy should explain whether the result is complete, approximate, best-so-far or unavailable when resources run out.

Check your understanding

A solver finds good solutions quickly in examples but has no guarantee of finding the optimum. Does this establish that the exact optimization problem is polynomial-time solvable?

Answer: No. The observed performance and approximate output do not provide the required general exactness and runtime guarantee.

Related terms

Computational complexity
Heuristic
Inference
polynomial time
NP-hardness
approximation algorithm
parameterised complexity

Learn next

Read computational complexity and approximation algorithm. For one AI task, state the input-size measure and required answer guarantee. Then identify which restrictions or compromises could make the workload manageable.

Computational complexity

Sources

Sedgewick and Wayne, Algorithms, intractability and complexity discussion: https://algs4.cs.princeton.edu/66intractability/

Peter Norvig, discussion of representation and inference efficiency in the author-hosted Paradigms of Artificial Intelligence Programming chapter: https://github.com/norvig/paip-lisp/blob/main/docs/chapter14.md

The relevant returned complexity and inference text was reviewed; the Princeton page could not be directly fetched. Growth-rate arithmetic and the fictional project are original illustrations. Practical performance is distinguished from formal worst-case tractability.

Previous: Tracking signal Next: Tragedy of the commons