A NON-DETERMINISTIC TURING MACHINE (NTM) DIFFERS FROM THE STANDARD MODEL IN ONE PLACE — THE TRANSITION FUNCTION RETURNS A **SET** OF POSSIBLE MOVES: δ : Q × Γ → P( Q × Γ × {L, R} ) At each step the machine may have SEVERAL applicable moves, or none. ── ACCEPTANCE ────────────────────────────────────────────── AN NTM ACCEPTS w IF **SOME** COMPUTATION PATH ACCEPTS. It rejects only if EVERY path rejects or fails to halt. The asymmetry is deliberate and total: ONE SUCCESSFUL PATH SUFFICES, however many others fail. TWO EQUIVALENT MENTAL MODELS, both useful: THE GUESSING MODEL — the machine always guesses the right move if a right move exists. It is an oracle for its own choices. THE PARALLEL MODEL — the machine splits into copies at each choice point, exploring all paths simultaneously in a COMPUTATION TREE, and accepts if any leaf accepts. NEITHER IS PHYSICALLY REALISABLE, and that is the point: an NTM is a MATHEMATICAL DEVICE FOR DEFINING COMPLEXITY CLASSES, not a machine anyone could build. ── THE COMPUTATION TREE ──────────────────────────────────── The natural picture: start / | \ / | \ c₁ c₂ c₃ ← choices at step 1 / \ / \ c₄ c₅ c₆ c₇ ← choices at step 2 ⋮ ⋮ REJECT ACCEPT ✓ · Each NODE is a configuration. · Each BRANCH is a non-deterministic choice. · The machine ACCEPTS if ANY leaf is accepting. · Branches may be infinite — a path that never halts. ── THE EQUIVALENCE THEOREM ───────────────────────────────── EVERY NON-DETERMINISTIC TURING MACHINE HAS AN EQUIVALENT DETERMINISTIC ONE. NON-DETERMINISM ADDS **NO COMPUTATIONAL POWER**. THE PROOF: SEARCH THE COMPUTATION TREE. A three-tape deterministic machine D simulates N: tape 1 — the input, never altered tape 2 — a working copy of N's tape for the current path tape 3 — the ADDRESS of the branch being explored, a string of digits saying which choice to make at each step D repeatedly: 1. copies the input to tape 2 2. simulates N, using tape 3 to decide each choice 3. if that path accepts, ACCEPT 4. otherwise write the next address on tape 3 and repeat THE CRITICAL DETAIL, AND THE ONE EXAMINERS TEST: THE SEARCH MUST BE **BREADTH-FIRST**, NOT DEPTH-FIRST. A depth-first search could descend an INFINITE non-halting branch and never return to explore a sibling branch that accepts. Breadth-first — trying all paths of length 1, then all of length 2, and so on — REACHES EVERY FINITE ACCEPTING PATH IN FINITE TIME. THIS IS THE SAME DOVETAILING PRINCIPLE AS IN THE ENUMERATOR TOPIC, applied to a tree rather than a list, and for exactly the same reason: A SINGLE NON-TERMINATING COMPUTATION MUST NEVER BE ALLOWED TO BLOCK THE REST. ── THE COST ──────────────────────────────────────────────── If N runs in time T(n) with branching factor at most b, the tree has up to b^T(n) nodes, and D must explore them all. SIMULATION TIME: O( b^T(n) ) — EXPONENTIAL. NUMERICALLY, with branching factor 2: depth 10 → 1,024 configurations depth 30 → 1,073,741,824 configurations and with branching factor 3 at depth 20, about 3.5 × 10⁹. SO NON-DETERMINISM COSTS EXPONENTIALLY IN TIME WHILE COSTING NOTHING IN POWER — and WHETHER THAT EXPONENTIAL COST IS NECESSARY IS PRECISELY THE P VERSUS NP QUESTION. ── SPACE IS DIFFERENT ────────────────────────────────────── A striking contrast, worth knowing: SAVITCH'S THEOREM: NSPACE( f(n) ) ⊆ DSPACE( f(n)² ) Non-determinism costs only a SQUARING in space, not an exponential. Consequently PSPACE = NPSPACE — the deterministic and non-deterministic polynomial SPACE classes are EQUAL. SO THE OPEN QUESTION IS SPECIFICALLY ABOUT TIME. For space, the analogous question was settled in 1970.

── THE DEFINITIONS ───────────────────────────────────────── P — problems DECIDABLE by a deterministic TM in polynomial time NP — problems decidable by a NON-DETERMINISTIC TM in polynomial time THE EQUIVALENT AND MORE USEFUL CHARACTERISATION OF NP: NP IS THE CLASS OF PROBLEMS WHOSE **SOLUTIONS CAN BE VERIFIED** IN POLYNOMIAL TIME. The two definitions match because the non-deterministic machine's accepting path IS the certificate: guessing it non-deterministically and verifying it deterministically are the same computation viewed from two sides. "NP" STANDS FOR **NON-DETERMINISTIC POLYNOMIAL**, NOT "NON-POLYNOMIAL". This is the most persistent misunderstanding in the subject and is worth stating explicitly in an exam answer. ── THE INTUITION ─────────────────────────────────────────── FINDING versus CHECKING. · Finding a Hamiltonian cycle in a graph seems to require searching exponentially many possibilities. · CHECKING a proposed cycle takes linear time — walk it and confirm every vertex appears once. · Finding the factors of a large number is hard. · CHECKING a proposed factorisation is one multiplication. · Finding a satisfying assignment for a Boolean formula is hard. · CHECKING one is a single evaluation. P ⊆ NP IS OBVIOUS: anything you can solve you can verify, by solving it again and comparing. WHETHER NP ⊆ P IS THE OPEN QUESTION — is checking really easier than finding, or have we simply not found the clever algorithms? ── WHY IT MATTERS ────────────────────────────────────────── THOUSANDS OF PROBLEMS ARE NP-COMPLETE — the hardest in NP, in the sense that a polynomial algorithm for any one of them would give a polynomial algorithm for all of them: Boolean satisfiability (SAT), travelling salesman, graph colouring, knapsack, scheduling, protein folding, circuit minimisation, and many more THEY ARISE INDEPENDENTLY ACROSS LOGISTICS, BIOLOGY, CHEMISTRY, CIRCUIT DESIGN AND OPERATIONS RESEARCH, which is why the question is not confined to theory. IF P = NP: · these thousands of problems all become efficiently solvable · MOST MODERN CRYPTOGRAPHY BREAKS, since it relies on problems being hard to solve and easy to verify · mathematics changes character, because finding a proof would be as easy as checking one IF P ≠ NP, as almost everyone believes: · these problems are genuinely intractable in the worst case, and the effort must go into approximation, heuristics and special cases — which is exactly what practice already does THE PROBLEM HAS BEEN OPEN SINCE COOK'S 1971 PAPER, AND NO APPROACH HAS COME CLOSE. Several proof techniques have been formally shown to be INCAPABLE of resolving it — relativisation, natural proofs, algebrisation — which is itself a remarkable body of work: we have proved that whole families of methods cannot settle the question. ── THE COMPARISON ACROSS THE MODELS ──────────────────────── MODEL DOES NON-DETERMINISM ADD POWER? ───────────────────────────────────────────────────────── FINITE AUTOMATON NO — subset construction (a set of states is finite) PUSHDOWN AUTOMATON **YES** — DPDA ⊊ NPDA (a set of stacks is infinite) TURING MACHINE NO — but at EXPONENTIAL time cost ───────────────────────────────────────────────────────── THIS PATTERN IS ONE OF THE MOST INSTRUCTIVE FACTS IN THE WHOLE SUBJECT. The answer is NO, YES, NO as one climbs the hierarchy — non-determinism matters in the middle and not at the ends, for entirely different reasons at each level. AT THE FINITE LEVEL, all possibilities can be tracked in the finite state. AT THE PUSHDOWN LEVEL, they cannot — there are infinitely many stack configurations. AT THE TURING LEVEL, they can be tracked again, because the unbounded tape can record the whole search — but the recording takes exponential time.