4.4.4.4–4.4.4.7 - Tractability and limits of computation

Complexity and available hardware

A computation may have a correct algorithm yet require more time or memory than the available system can provide. Hardware imposes practical limits through processing rate, memory capacity and storage. Algorithmic complexity determines how the required resources grow as the input size increases.

Suppose a method examines every one of $2^n$ possibilities, using one operation for each, on a simplified machine performing $10^9$ operations per second. For n = 30, the time is about 1.07 seconds. For n = 60, it is about $1.15\times10^9$ seconds: approximately 36.6 years, using 365.25 days per year. This is an idealised estimate; it ignores extra work and memory limits, so it is not a prediction for a real implementation.

A machine 1000 times faster reduces that second time to about 13.3 days. It improves the constant factor without changing exponential growth. Increasing n by just 10 multiplies the number of possibilities by $2^{10}=1024$, almost consuming the entire hardware improvement. An improved algorithm with a slower growth rate can therefore matter more than a faster processor.

Memory matters separately. An algorithm might run quickly enough but require a table too large for available RAM. A system might trade recomputation for storage, but the resulting time cost must also be considered. “Possible in principle” and “feasible for this input on this hardware” are different claims.

Tractability, intractability and heuristics

A tractable problem has a solution algorithm taking polynomial time or less as a function of input size. Constant, logarithmic and linear time are included, as are polynomial bounds such as $O(n^2)$ or $O(n^3)$. A polynomial has a fixed exponent: the exponent does not itself grow with n.

Exponential search is not polynomial, but finding one exponential algorithm does not prove that the problem is intractable. A faster solution may exist. For example, an unnecessarily exhaustive method for finding the largest value can be replaced by a linear scan, so the problem is tractable even if that first method was very poor. Distinguish a slow algorithm from a problem for which no polynomial solution exists.

If no polynomial solution is known, say so rather than presenting this as proof that none exists. Some familiar optimisation problems have exact methods with prohibitive growth, while the existence of a polynomial-time exact solution remains unresolved. This lesson does not require resolving those open questions.

Tractable is a growth classification, not a promise that every instance is practical. $n^{100}$ is polynomial but may be unusable for the required input; a small instance of an exponential method may finish quickly. Time limits, input sizes and constants remain relevant.

A heuristic uses a practical rule to find a useful answer without guaranteeing the exact optimum. A delivery planner might repeatedly choose a nearby unvisited destination instead of examining every possible tour. It can obtain a route quickly, but a locally attractive step may lead to a poor overall route. A valid route and the shortest route are different outcomes.

The value of a heuristic depends on the goal: producing a sufficiently good answer before a deadline may be preferable to waiting for an exact optimum. State what is sacrificed, such as guaranteed optimality; do not claim that a heuristic proves the original problem tractable or always returns the best answer.

Computability and the Halting problem

A computable problem admits an algorithm that supplies the required answer for every permitted input. Some problems are not computable: there is no algorithm that always terminates with the correct answer for every instance. This is a logical limit on algorithmic solutions, rather than just a shortage of processing time.

The general Halting problem is undecidable. No universal algorithm can always terminate and correctly classify every possible program–input pair. The input matters: a program may halt for one supplied value and loop forever for another. The question is whether it eventually stops, not whether it produces a useful or correct result.

This does not mean that we cannot analyse any individual program. A fixed sequence of a few operations can plainly finish, and an unconditional loop with no exit can plainly continue forever. The impossibility concerns one method guaranteed to decide all cases. A program analyser can decide restricted classes or provide useful warnings while still failing to settle every arbitrary case.

Running a program does not solve the general problem. If it stops, that run establishes halting for that input. If it has run for an hour, a day or any other finite time without stopping, it may still stop later. A timeout records “did not halt within this limit”, rather than proving “will never halt”.

An intractable but computable problem has an algorithmic solution whose resource requirements can be prohibitive. The general Halting problem has no deciding algorithm at all. Faster processors, more RAM or a different programming language do not remove this theoretical limit. The result establishes that there are questions a computer cannot solve algorithmically in general, even if idealised resource limits are lifted.

The specification requires you to describe the Halting problem and explain its significance; a proof is not required. Keep the universal claim precise rather than attempting to prove it by showing just one long-running program.