Optimisation and Tractability

Most of this course has asked "what is the best algorithm for a problem?" This lesson asks a harder and more humbling question: are there problems for which no efficient algorithm exists — or for which no algorithm exists at all? This is the domain of computational methods in OCR H446 section 2.2.2: the study of which problems are tractable (solvable in a reasonable, polynomial amount of time), which are intractable (technically solvable but only with explosive, exponential effort), and which — like the famous halting problem — are flatly undecidable. Understanding these limits is what separates a programmer who throws ever-faster hardware at a problem from one who recognises when a different approach is the only hope.

That different approach is the practical heart of the lesson. When a problem is intractable we cannot demand the perfect answer, so we turn to heuristics (clever rules that find good-enough answers fast), backtracking (systematic trial-and-error that abandons dead ends early), and performance modelling (estimating cost before committing resources). These three techniques are explicitly examined, so this lesson treats them in depth alongside the theory. Throughout, the vocabulary of growth rates from the Big-O lesson — polynomial versus exponential — is the language we reason in.

---

Spec Mapping

This lesson supports OCR H446 section 2.2.2 (computational methods) and the related ideas on the limits of computation. Paraphrased, the assessable ideas are:

• Distinguishing tractable problems (a polynomial-time solution exists) from intractable ones (only super-polynomial solutions are known), using the polynomial-versus-exponential growth distinction.
• Understanding that some problems have no efficient solution, and that some — exemplified by the halting problem — are undecidable, so no algorithm can solve them at all.
• Explaining and applying heuristic methods to obtain good-enough solutions to otherwise infeasible problems.
• Understanding backtracking as a systematic search strategy and performance modelling as a way to predict an algorithm's resource needs before running it.

This is a paraphrase; verify wording against the current OCR H446 specification.

---

Tractable vs Intractable Problems

A problem is tractable if there is an algorithm that solves it in polynomial time — its worst-case complexity is $O(n^k)$O(nk) for some fixed constant $k$k (so $O(n)$O(n), $O(n^2)$O(n2), $O(n^3)$O(n3) all count). Polynomial growth, however steep, scales in a manageable way: hardware improvements and clever engineering keep these problems within reach even for large inputs.

Tractable problem	Complexity
Sorting a list (merge sort)	$O(n \log n)$O(nlogn)
Searching a sorted array (binary search)	$O(\log n)$O(logn)
Shortest path (Dijkstra)	$O((V+E)\log V)$O((V+E)logV)
Matrix multiplication	$O(n^3)$O(n3)

A problem is intractable if the best known algorithm needs more than polynomial time — typically exponential $O(2^n)$O(2n) or factorial $O(n!)$O(n!). The phrase "best known" matters: for most of these problems, nobody has proved that no polynomial algorithm exists, but none has ever been found, and the practical effect is the same — they are infeasible beyond small inputs.

Intractable problem (brute force)	Complexity
Travelling Salesman Problem	$O(n!)$O(n!)
0/1 Knapsack Problem	$O(2^n)$O(2n)
Boolean Satisfiability (SAT)	$O(2^n)$O(2n)
Tower of Hanoi (number of moves)	$O(2^n)$O(2n)

Feature	Tractable	Intractable
Growth	Polynomial — a hill	Exponential/factorial — a cliff
Scalability	Copes with large $n$n	Hits a wall almost immediately
Hardware helps?	Yes, meaningfully	Barely — a faster machine adds a few inputs

The last row deserves emphasis because it is a favourite exam point. Doubling your processor speed lets a polynomial algorithm handle noticeably larger inputs, but for an $O(2^n)$O(2n) algorithm it lets you handle just one more input (since one extra input doubles the work, exactly cancelling the doubled speed). You cannot buy your way out of intractability with hardware; you must change the approach.

---

Why Exponential Growth Becomes Infeasible (Worked Illustration)

It is one thing to say "exponential is bad" and another to feel how bad. Take a brute-force algorithm of complexity $T(n) = 2^n$T(n)=2n operations, running on a fast machine that performs $10^9$109 (one billion) operations per second. The time to finish is $T(n)/10^9$T(n)/109 seconds. Watch what happens as $n$n creeps up:

$n$n	Operations $2^n$2n	Time at $10^9$109/sec
10	$\approx 10^3$≈103	~1 microsecond
30	$\approx 10^9$≈109	~1 second
50	$\approx 10^{15}$≈1015	~13 days
60	$\approx 1.15 \times 10^{18}$≈1.15×1018	~36 years
70	$\approx 1.18 \times 10^{21}$≈1.18×1021	~37,000 years
100	$\approx 1.27 \times 10^{30}$≈1.27×1030	longer than the age of the universe

The decisive feature is that each extra input doubles the running time: going from $n$n to $n+1$n+1 turns 36 years into 72. Contrast a polynomial $O(n^3)$O(n3) algorithm on the same machine: at $n = 100$n=100 it needs $10^6$106 operations — a millisecond — and at $n = 1000$n=1000 only $10^9$109 operations — one second. The factorial case $O(n!)$O(n!) is worse still, because $n! = n \times (n-1)!$n!=n×(n−1)! multiplies by $n$n (not just 2) at each step:

$10! = 3{,}628{,}800, \qquad 20! \approx 2.4 \times 10^{18}, \qquad 60! \approx 8.3 \times 10^{81}$10!=3,628,800,20!≈2.4×1018,60!≈8.3×1081

— and $60!$60! exceeds the estimated number of atoms in the observable universe. This is why an exponential or factorial problem is called intractable: not because we are not clever enough to run it, but because no conceivable computer, however fast, can push the feasible $n$n much past a few dozen.

---

The Travelling Salesman Problem (TSP)

The TSP is the canonical intractable optimisation problem:

Given a set of cities and the distance between each pair, find the shortest possible route that visits every city exactly once and returns to the start.

Why it is hard

Brute force tries every ordering of the cities. For $n$n cities on an undirected map the number of distinct routes is $\tfrac{(n-1)!}{2}$2(n−1)!​, which is factorial growth:

Cities $n$n	Distinct routes $\tfrac{(n-1)!}{2}$2(n−1)!​	Time at $10^9$109 routes/sec
5	12	instant
10	181,440	instant
15	$\approx 4.4 \times 10^{10}$≈4.4×1010	~44 seconds
20	$\approx 6 \times 10^{16}$≈6×1016	~2 years
25	$\approx 3.1 \times 10^{23}$≈3.1×1023	~10 million years

No polynomial-time algorithm for the optimal TSP is known, and the problem is NP-hard. Yet real logistics companies route thousands of vehicles daily — they do it with the heuristics and approximation methods covered below, accepting a route that is provably near-optimal rather than insisting on the exact best. This gap between "theoretically intractable" and "routinely handled in practice" is one of the most important lessons of the whole topic: intractability does not mean a problem is useless or ignored, only that we must relax our demands — usually by giving up the guarantee of the perfect answer in exchange for a good answer delivered quickly. The art of computer science, faced with an intractable problem, is choosing which compromise (a heuristic, an approximation with a quality bound, an exact method limited to small inputs, or a problem-specific shortcut) best fits the situation at hand.

---

The Halting Problem: a Problem With No Algorithm at All

Intractable problems are merely slow; the halting problem is impossible. It asks an apparently reasonable question:

Given any program and any input, decide whether that program will eventually halt (finish) or run forever.

A universal "halt checker" would be hugely useful — it could catch infinite loops before they ship. Alan Turing proved in 1936 that no such algorithm can exist: the halting problem is undecidable.

Proof by contradiction (high level)

1. Suppose a function halts(program, input) exists that always returns true if program halts on input and false if it loops forever.
2. Build a mischievous routine that uses it:

# OCR-style pseudocode
function paradox(program)
    if halts(program, program) then
        loop forever        // if it WOULD halt, we deliberately don't
    else
        return              // if it WOULD loop, we deliberately halt
    endif
endfunction

3. Now ask the fatal question: does paradox(paradox) halt?
   • If halts(paradox, paradox) says true (it halts), then paradox enters loop forever — so it does not halt. Contradiction.
   • If halts(paradox, paradox) says false (it loops), then paradox takes the return branch — so it does halt. Contradiction.
4. Either answer is self-contradictory, so the assumption in step 1 must be false: halts cannot exist.

What it means

• There are fundamental limits to computation — some questions no algorithm can ever answer for all inputs.
• Undecidable is stronger than intractable: an intractable problem can be solved, just slowly; an undecidable one cannot be solved by any algorithm at all.
• It does not mean we cannot analyse specific programs — only that no single universal checker works for every program. (This is why real tools detect many infinite loops but can never promise to catch them all.)

---

Complexity Classes: P, NP and Beyond

Computer scientists group problems by difficulty into complexity classes.

• P (polynomial time) — problems solvable in polynomial time. These are the tractable problems: sorting, searching, shortest paths.
• NP (nondeterministic polynomial time) — problems whose proposed solution can be verified in polynomial time, even if finding one might take exponential time. The TSP (as a decision problem), Sudoku, graph colouring and SAT are in NP: given a candidate answer you can quickly check it, but discovering it seems to need a search.

The "verify versus solve" distinction is the crux, and an everyday analogy makes it stick. A completed Sudoku grid is trivial to check — scan each row, column and box for duplicates, which takes time proportional to the grid size. But finding the solution from a blank-ish grid seems to require search. A jigsaw is similar: confirming a finished puzzle is correct takes a glance, yet assembling it took effort. NP is the class of problems with this "easy to check, seemingly hard to find" character. The deep question is whether that appearance is real — whether finding is genuinely harder than checking, or whether we simply have not yet discovered the clever fast algorithms.

Every problem in P is also in NP (if you can solve quickly you can certainly verify quickly — solving hands you the very solution you would check). The billion-dollar open question is the reverse:

Does P = NP?

This is one of the great unsolved problems in mathematics. Informally: if a solution can be checked quickly, can it always be found quickly?

If P = NP (thought unlikely)	If P ≠ NP (widely believed)
Every quickly-verifiable problem is also quickly solvable	Some problems are inherently harder to solve than to verify
Much modern encryption would collapse (factoring etc. would be easy)	Encryption based on hard problems stays secure
Many intractable problems become tractable	Intractable problems remain intractable

Most researchers believe P ≠ NP, but it has never been proven — and a great deal of practical security quietly assumes it.

NP-Complete and NP-Hard

• NP-Complete problems are the hardest problems in NP: every NP problem can be transformed into them. If any NP-Complete problem had a polynomial solution, all of NP would, proving P = NP. The TSP decision version, SAT, graph colouring, knapsack and subset-sum are NP-Complete.
• NP-Hard problems are at least as hard as NP-Complete problems but need not be in NP themselves (their solutions may not even be verifiable in polynomial time). The optimisation TSP is NP-hard.

flowchart TB
    NPH["NP-Hard (at least as hard as everything in NP)"]
    NP["NP — verifiable in polynomial time"]
    NPC["NP-Complete — the hardest problems in NP"]
    P["P — solvable in polynomial time"]
    NPH --> NPC
    NP --> NPC
    NP --> P

(The diagram reflects the widely-believed assumption that P ≠ NP, under which P is a strict subset of NP.)

---

Heuristics: Trading Optimality for Feasibility

If a problem is intractable, demanding the perfect answer is hopeless for large inputs. A heuristic abandons that demand: it is a practical rule-of-thumb that finds a good-enough (often near-optimal) solution quickly, without any guarantee of optimality. Heuristics are how intractable problems are tackled in the real world every single day.

Heuristic method	Idea	Typical use
Greedy	Take the locally best choice at each step	Nearest-neighbour for TSP
Hill climbing	Repeatedly make a small change that improves the solution	Function/parameter optimisation
Simulated annealing	Like hill climbing but sometimes accept a worse move early on to escape local optima	Scheduling, circuit layout
Genetic algorithms	"Evolve" a population of solutions via selection, crossover and mutation	Complex multi-variable optimisation

Worked example: nearest-neighbour for the TSP

A simple greedy heuristic for the TSP:

1. Start at any city, mark it visited.
2. Repeatedly travel to the NEAREST unvisited city; mark it visited.
3. When all cities are visited, return to the start.

This runs in $O(n^2)$O(n2) — comfortably tractable — instead of the brute force $O(n!)$O(n!). The price is optimality: nearest-neighbour can be misled into an expensive final leg and typically produces a route perhaps 25% longer than the true optimum. That is the universal heuristic bargain.

The local-optimum trap

Greedy and hill-climbing heuristics share a weakness worth understanding: they can get stuck at a local optimum — a solution better than all its near neighbours but worse than the global best — because every small change makes things worse, even though a large change would help. Simulated annealing and genetic algorithms are popular precisely because their controlled randomness lets them occasionally accept a worse step and so escape such traps.

Optimal (exact) solution	Heuristic solution
Guaranteed best answer	Possibly suboptimal (no guarantee)
Often exponential time	Polynomial time
Feasible only for small $n$n	Feasible for large $n$n

Synoptic note. Be careful to distinguish a heuristic here (which sacrifices optimality to beat intractability) from the heuristic in A* search (which only reorders the search and so keeps optimality). Same word, importantly different role.

---

Backtracking: Systematic Trial and Error