Decidability and Complexity — The Halting Problem, Reductions, Rice's Theorem, P vs NP and NP-Completeness

Some problems can't be solved by any program, no matter how clever or how fast the computer. Others can be solved in principle but seem to need impossible amounts of time. This lesson covers both kinds of limits — the most important ideas in all of computer science theory.

1. Decidable and undecidable

A problem (language) is decidable if some algorithm always halts with the correct yes/no answer.

2. The halting problem

HALT = {⟨P, w⟩ : program P halts on input w}. No program can decide HALT.

Proof by contradiction (Turing, 1936), in Python-flavoured pseudocode. Suppose someone gives us a perfect function:

def halts(program_source, input_data):
    """Magic: returns True if program halts on input, False if it loops forever."""
    ...

Now write this program:

def paradox(src):
    if halts(src, src):        # would this program halt when given its own source?
        while True:            # ...then loop forever
            pass
    else:
        return "done"          # ...otherwise halt

Run paradox on its own source code:

• If halts(paradox, paradox) says True, then paradox loops forever — so the answer was wrong.
• If it says False, then paradox halts — wrong again.

Either way halts is wrong, so a perfect halts cannot exist. ∎

This is diagonalisation — the same trick Cantor used to show there are more real numbers than integers. HALT is recognisable (just run P and accept if it halts) but not decidable; its complement is not even recognisable.

Practical meaning: no tool can perfectly detect infinite loops, dead code, or all bugs. Linters, type checkers and static analysers must either miss some problems or raise false alarms — and that's a theorem, not a lack of effort.

3. Reductions

To prove a new problem B is undecidable, reduce a known undecidable problem A to it: show that a decider for B could be used to build a decider for A. Since A has no decider, B can't either.

Example: "Does program P print 'hello' on some input?" If we could decide this, we could decide HALT: build P′ that runs P on w (with all printing removed) and then prints "hello". P′ prints "hello" ⇔ P halts on w.

Reductions are also how complexity results are proved (section 6).

4. Rice's theorem

Every non-trivial property of the language (behaviour) of a program is undecidable.

"Non-trivial" = some programs have it and some don't. So: "does this program accept only even numbers?", "does it ever return 42?", "is its output always sorted?" — all undecidable in general. Properties of the code text (e.g. "has more than 100 lines") are fine; properties of what it computes aren't.

5. Complexity: decidable but feasible?

Now consider problems we can solve, and ask how fast. Time is measured as a function of input size n.

Solve vs verify — the heart of NP. For SAT (is there an assignment making a Boolean formula true?), checking a given assignment is fast, but the obvious way to find one tries all 2ⁿ assignments:

from itertools import product
import time

# (x1 or not x2 or x3) and (not x1 or x2) and (x2 or not x3) and (not x2 or not x3 or x1)
clauses = [[1, -2, 3], [-1, 2], [2, -3], [-2, -3, 1]]

def verify(assign, clauses):                     # polynomial: one pass over the clauses
    return all(any(assign[abs(l)] == (l > 0) for l in c) for c in clauses)

def brute_force_sat(clauses, n):                 # exponential: tries up to 2^n assignments
    for bits in product([False, True], repeat=n):
        assign = dict(enumerate(bits, start=1))
        if verify(assign, clauses):
            return assign
    return None

sol = brute_force_sat(clauses, 3)
print("satisfying assignment:", sol, "| verified:", verify(sol, clauses))

for n in [10, 15, 20]:
    print(f"n = {n:2}: up to {2 ** n:>9,} assignments to try")
print("n = 100: up to", f"{2 ** 100:.2e}", "assignments - longer than the age of the universe")

satisfying assignment: {1: False, 2: False, 3: False} | verified: True
n = 10: up to     1,024 assignments to try
n = 15: up to    32,768 assignments to try
n = 20: up to 1,048,576 assignments to try
n = 100: up to 1.27e+30 assignments - longer than the age of the universe

6. P vs NP

Everything in P is in NP (if you can solve it fast, you can verify fast). Is P = NP? — can every efficiently verifiable problem also be solved efficiently? Nobody knows. It's one of the seven Millennium Prize Problems (US$1 million prize). Most researchers believe P ≠ NP.

Cook–Levin theorem: SAT is NP-complete. Since then thousands of problems have been shown NP-complete by reductions from SAT or from each other. If any one NP-complete problem had a polynomial algorithm, all of NP would — so P = NP.

Why it matters:

• Cryptography relies on some problems being hard (factoring, discrete logarithms — not known NP-complete, but believed outside P for classical computers).
• Optimisation (scheduling, routing, timetabling, chip design) — many real problems are NP-hard, so industry uses approximation algorithms, heuristics, SAT/ILP solvers and exploits structure in real inputs.
• In interviews, recognising "this is NP-hard" (e.g. TSP, subset sum, graph colouring) tells you to look for constraints, DP on small parameters (like knapsack's pseudo-polynomial O(n·W)), or approximations — not a magic polynomial algorithm.

7. The big picture of the track

Common mistakes

• "NP" means "non-polynomial" — wrong: it means nondeterministic polynomial (verifiable in polynomial time).
• Thinking NP-hard problems are always in NP (the halting problem is NP-hard but undecidable).
• Believing the halting problem is just hard — it's impossible for any algorithm.
• Applying Rice's theorem to syntactic properties of code (it's only about behaviour).

Quick recap

• Decidable = an always-halting algorithm exists. HALT is undecidable (diagonalisation: the program that does the opposite of the prediction).
• Reductions transfer undecidability/hardness; Rice: every non-trivial behavioural property is undecidable.
• P = solvable fast; NP = verifiable fast; NP-complete = hardest in NP (SAT, 3-SAT, Hamiltonian cycle…); NP-hard = at least that hard.
• P vs NP is open; one polynomial NP-complete algorithm ⇒ P = NP.