Optimisation and Tractability

This lesson covers tractability, the halting problem, and complexity classes — topics that explore the fundamental limits of computation. These are required by the OCR A-Level Computer Science (H446) specification.

---

Tractable vs Intractable Problems

Tractable Problems

A problem is tractable if it can be solved in polynomial time — that is, its time complexity is O(n^k) for some constant k (e.g., O(n), O(n^2), O(n^3)).

Example	Time Complexity	Tractable?
Sorting a list	O(n log n)	Yes
Searching a sorted array	O(log n)	Yes
Shortest path (Dijkstra's)	O(V^2) or O((V+E) log V)	Yes
Matrix multiplication	O(n^3)	Yes

Intractable Problems

A problem is intractable if the best known algorithm requires more than polynomial time — typically exponential O(2^n) or factorial O(n!) time.

Example	Time Complexity	Tractable?
Travelling Salesman Problem (brute force)	O(n!)	No
Knapsack Problem (brute force)	O(2^n)	No
Boolean Satisfiability (general)	O(2^n)	No
Tower of Hanoi	O(2^n)	No

Key Distinction

Feature	Tractable	Intractable
Growth rate	Polynomial — manageable	Exponential/factorial — explosive
Scalability	Can handle large inputs	Becomes impractical quickly
n = 100	Seconds to minutes	Years to universe-lifetimes

---

The Travelling Salesman Problem (TSP)

The TSP is a classic intractable problem:

Given a list of cities and the distances between them, find the shortest route that visits every city exactly once and returns to the starting city.

Why Is It Hard?

The number of possible routes for n cities is (n-1)!/2 (for undirected graphs).

Cities (n)	Possible Routes	Time (at 1 billion routes/sec)
5	12	Instant
10	181,440	Instant
15	~43 billion	~43 seconds
20	~60 quadrillion	~2 years
25	~310 sextillion	~10 million years

No polynomial-time algorithm is known for the TSP.

---

The Halting Problem

The halting problem asks: "Given a program and an input, will the program eventually halt (finish), or will it run forever?"

Alan Turing's Proof (1936)

Alan Turing proved that the halting problem is undecidable — there is no algorithm that can solve it for all possible programs and inputs.

Proof by Contradiction (Simplified)

1. Assume a function halts(program, input) exists that returns true if the program halts on the given input, and false otherwise.
2. Construct a new program paradox:

function paradox(program)
    if halts(program, program) then
        loop forever    // don't halt
    else
        return          // halt
    endif
endfunction

3. Now consider: what happens when we call paradox(paradox)?
   • If halts(paradox, paradox) returns true (paradox halts), then paradox loops forever — contradiction!
   • If halts(paradox, paradox) returns false (paradox doesn't halt), then paradox halts — contradiction!
4. Both cases lead to a contradiction, so the halts function cannot exist.

Significance

• The halting problem shows there are limits to what computers can compute.
• Some problems are fundamentally unsolvable by any algorithm.
• This does not mean we cannot check specific programs — it means no universal checker exists.

Exam Tip: The halting problem is a common exam topic. Be able to explain the proof by contradiction at a high level and state its significance: some problems are undecidable — no algorithm can solve them for all cases.

---

Complexity Classes

Computational problems are classified into complexity classes based on how hard they are to solve.

P (Polynomial Time)

P is the class of problems that can be solved in polynomial time by a deterministic Turing machine.

Properties	Description
Solvable in	O(n^k) time
Examples	Sorting, searching, shortest path, matrix multiplication
Significance	These are the "efficiently solvable" problems

NP (Nondeterministic Polynomial Time)