Limits of Computation and Tractability

Even with unlimited hardware speed, not every problem can be solved efficiently — or at all. Two types of limits:

1. Complexity limits — the algorithm exists but takes too long for large inputs (e.g. exponential-time algorithms are impractical)
2. Computability limits — no algorithm can exist for some problems, regardless of time or hardware

Why complexity matters in practice:

Algorithm class	Growth for $n=1000$	Practical?
$O(n)$	1 000 operations	Yes
$O(n^2)$	1 000 000 operations	Yes
$O(n^3)$	$10^9$ operations	Marginal
$O(2^n)$	$10^{301}$ operations	No — infeasible
$O(n!)$	astronomically large	No — infeasible

Both hardware improvements and better algorithms extend what is practically computable — but exponential and factorial problems remain out of reach for even modest $n$.

Tractable problem — a problem for which a polynomial-time algorithm exists (complexity $O(n^k)$ for some constant $k$). These are considered "efficiently solvable" in practice.

Examples of tractable problems:

• Sorting a list: $O(n\log n)$
• Searching a sorted array: $O(\log n)$
• Finding shortest paths in a graph (Dijkstra): $O(E\log V)$

Intractable problem — a problem for which no polynomial-time algorithm is currently known. The best known algorithms are exponential or worse.

Examples of intractable problems:

• Travelling Salesman Problem (TSP): find the shortest route visiting all $n$ cities exactly once — brute force $O(n!)$; no known polynomial solution
• Boolean satisfiability (SAT): determine if a Boolean formula can be satisfied — $O(2^n)$ brute force
• Protein folding: determining a protein's 3D structure from its amino acid sequence

Key distinction: tractable = polynomial time; intractable = no known polynomial-time solution.

Since intractable problems cannot be solved optimally in reasonable time, heuristic methods are used to find good-enough solutions quickly.

A heuristic is an approach that:

• Does not guarantee the optimal solution
• Runs in acceptable (usually polynomial) time
• Typically produces a near-optimal solution

Example — TSP nearest-neighbour heuristic:

1. Start at any city
2. Repeatedly travel to the nearest unvisited city
3. Return to the start

This gives a solution in $O(n^2)$, but it is not guaranteed to be the shortest possible route — it may be 20–25% longer than optimal. For most real applications (delivery routing, circuit board design), "close enough fast" beats "perfect but never finished."

Other heuristic techniques: genetic algorithms, simulated annealing, ant colony optimisation.

Not all problems are solvable by any algorithm, regardless of time.

Computable problem — a problem for which an algorithm exists that terminates with the correct answer for all valid inputs. Most everyday programming tasks are computable.

Non-computable problem — no algorithm can solve the problem for all possible inputs. These are not just hard — they are provably unsolvable.

Why non-computable problems exist:

• The set of all possible programs is countably infinite (programs are finite strings)
• The set of all possible problems (functions from inputs to outputs) is uncountably infinite
• Therefore, most problems cannot be solved by any program

The most famous non-computable problem is the halting problem.

The halting problem asks: given an arbitrary program $P$ and an input $I$, will $P$ eventually stop (halt) when run on $I$?

Alan Turing proved in 1936 that no general algorithm can solve this for all programs and inputs.

Proof sketch (by contradiction): AQA requires awareness of the result — not the ability to reproduce the proof.

1. Suppose a HALTS(P, I) function exists that returns True if $P$ halts on $I$, False otherwise
2. Construct a new program PARADOX that calls HALTS(PARADOX, PARADOX):
   • If HALTS returns True (PARADOX halts), PARADOX loops forever
   • If HALTS returns False (PARADOX doesn't halt), PARADOX halts immediately
3. In both cases, the result contradicts the output of HALTS — a logical impossibility
4. Therefore, no such HALTS function can exist

Significance:

• Proves that some problems are non-computable — not just hard, but provably unsolvable
• Limits what software tools (compilers, static analysers) can guarantee about programs
• Underpins the theory of what computers can and cannot do

Most day-to-day software sits in the "tractable" category. The boundaries matter for:

• Security (brute-force attacks rely on intractability of factoring large numbers)
• AI (many optimisation problems are intractable; heuristics are essential)
• Formal verification (halting problem limits what we can prove about software)

1. Confusing intractable with non-computable

An intractable problem has an algorithm — it just takes too long for large inputs. A non-computable problem has no algorithm at all. These are different categories.

2. Stating that heuristics always find the optimal solution

Heuristics find good solutions quickly but do not guarantee optimality. An exam answer claiming "the nearest-neighbour heuristic finds the shortest route" is factually incorrect.

3. Claiming the halting problem is just "very hard to solve"

The halting problem is provably unsolvable — no algorithm can solve it for all inputs. It is not a matter of needing a faster computer or better algorithm.

4. Misidentifying polynomial vs exponential complexity

$O(n^3)$ is polynomial (tractable); $O(3^n)$ is exponential (intractable). The key distinction: in polynomial complexity, $n$ is the base; in exponential, $n$ is the exponent.