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

Source: https://skills101.in/learn/theory-of-computation/decidability-halting-p-vs-np — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-09.

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.

| Decidable | Undecidable |
|---|---|
| Does this DFA accept string w? | Does this program halt on input w? (**halting problem**) |
| Is this DFA's language empty? | Do two programs compute the same function? |
| Is w generated by this CFG? (CYK) | Is this CFG ambiguous? |
| Is n prime? | Does this program ever print "hello"? |

## 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:

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

Now write this program:

```python
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**. ∎

![The halting paradox: a program asks the supposed halting decider about itself and then does the opposite, so whatever the decider answers is wrong; therefore no halting decider can exist](https://skills101.in/learn-img/theory-of-computation/halting.svg)

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.

| Class | Meaning | Examples |
|---|---|---|
| **P** | solvable in **polynomial** time (n, n², n³ …) | sorting, shortest paths, primality testing, matching |
| **NP** | a proposed answer can be **verified** in polynomial time | SAT, travelling salesperson (decision), Sudoku, graph colouring, subset sum |
| **NP-complete** | in NP, and **every** NP problem reduces to it | SAT, 3-SAT, Hamiltonian cycle, vertex cover, subset sum |
| **NP-hard** | at least as hard as every NP problem (may not be in NP) | TSP optimisation, halting problem |

![Complexity classes assuming P is not equal to NP: P sits inside NP, NP-complete problems are the hardest problems inside NP, and NP-hard extends beyond NP; if any NP-complete problem had a polynomial algorithm, P would equal NP](https://skills101.in/learn-img/theory-of-computation/complexity-classes.svg)

**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:

```python
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")
```

```text
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

| Machine | Languages | Can't do |
|---|---|---|
| DFA / NFA / regex | regular | counting/nesting (aⁿbⁿ) |
| PDA / CFG | context-free | aⁿbⁿcⁿ, ww |
| Turing machine | recognisable; decidable if it always halts | halting problem, Rice properties |
| Polynomial-time TM | P | NP-complete problems (unless P = NP) |

## 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.


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/decidability-halting-p-vs-np