Nondeterminism and Certificates

Branching computation, polynomial verification, and the equivalence of two views of NP.

Goals

• Define acceptance for nondeterministic machines.
• Translate between accepting branches and certificates.
• Avoid confusing nondeterminism with randomness.

Intuition

A nondeterministic decider accepts when at least one legal branch accepts. Equivalently, a short certificate lets a deterministic verifier check a yes-instance efficiently.

Formal definitions

A nondeterministic machine runs in time $t(n)$ if every branch halts within $t(n)$. The class

A nondeterministic transition relation may offer several legal moves from one configuration. A computation tree has the initial configuration at its root and one child for each legal successor. The machine accepts if at least one branch accepts and rejects only if all branches reject. Nondeterminism assigns no probabilities to branches.

For general bounds,

and $\mathrm{NSPACE}(s(n))$ is defined analogously using at most $O(s(n))$ work cells on every branch. Every branch must halt for an NTM decider. A single infinite branch invalidates a claimed time bound, even if another branch accepts quickly.

Trace one accepting root-to-leaf path and record its edge labels. That string is a certificate of choices. Then inspect a no-instance: there must be no accepting leaf anywhere.

A polynomial verifier for $L$ is a deterministic polynomial-time $V$ and polynomial $p$ such that

Theorem. The nondeterministic-machine and polynomial-verifier definitions of $\mathrm{NP}$ are equivalent.

Proof walkthrough

We prove both directions. Assume a standard multitape model and that deciders/verifiers halt.

Direction I — NTM to verifier. Let $N$ decide $L$ in nondeterministic time $p(n)$. Each configuration has at most $b$ children ($b$ fixed for $N$). Encode each transition choice in $O(1)$ bits. A certificate $y$ is the choice string along a branch of length $\le p(|x|)$, so $|y|\le O(p(|x|))$.

The verifier $V(x,y)$ simulates $N$ on $x$ according to $y$: at each step it reads the next choice, rejects if the choice is illegal or $y$ ends before halt, and accepts only if the simulation reaches an accepting state within $p(|x|)$ steps. Deterministic time is polynomial in $|x|+|y|$.

Completeness: if $x\in L$ some accepting branch exists; its choice encoding is an accepting certificate. Soundness: every accepted certificate describes a genuine accepting branch of $N$.

Direction II — verifier to NTM. Given verifier $V$ and polynomial $q$ with $x\in L$ iff some $|y|\le q(|x|)$ has $V(x,y)=1$, the NTM $N$ guesses a string of length $\le q(|x|)$ bit by bit, then runs $V$ deterministically. If $x\in L$ some guess accepts; if $x\notin L$ every guess rejects. The length bound is essential: without it, even reading an exponential witness is not polynomial in $|x|$.

What this does not show. Equivalence does not give a deterministic polynomial simulation, nor settle $\mathrm{NP}=\mathrm{coNP}$.

Computation-tree size and deterministic simulation

Suppose each configuration has at most $b$ successors and every branch has length at most $t(n)$. The tree can contain

nodes for constant $b>1$. A deterministic simulator can traverse this tree depth-first, simulate every branch, and accept if one leaf accepts. Therefore

for standard fixed-branching models and reasonable constructible $t$. In particular,

The first inclusion lets a deterministic machine be an NTM with one choice. The second explores all polynomial-length choice strings.

This simulation is exponential in time, not polynomial merely because each branch is polynomial. The number of branches, not just branch depth, matters.

For space, naive depth-first exploration of a computation tree may encounter cycles and potentially infinite branches. Configuration graphs supply the correct finite object. An NTM using $s(n)\ge\log n$ space has $2^{O(s(n))}$ configurations. Acceptance asks whether an accepting configuration is reachable from the start configuration. Deterministically exploring this graph yields

by a straightforward simulation. A much stronger theorem, Savitch's theorem, gives

for $s(n)\ge\log n$, but its recursive reachability proof is beyond the basic tree enumeration used here. Consequently $\mathrm{NPSPACE}=\mathrm{PSPACE}$.

Space semantics

Space is measured on the largest branch footprint, not by adding space across simultaneous branches. The computation tree is mathematical semantics; the NTM does not physically store all branches at once. A branch may reuse work cells, so exponential time can coexist with polynomial space.

Define

Clearly $\mathrm{PSPACE}\subseteq\mathrm{NPSPACE}$. Savitch's theorem supplies the reverse containment after squaring a polynomial.

Worked example

For Hamiltonian cycle, a certificate is an ordering of all vertices. Check that every vertex appears once and each consecutive pair, including the last-first pair, is an edge. The check is polynomial in the graph encoding.

If vertices are numbered $1,\ldots,m$, the witness contains $m$ numbers of $O(\log m)$ bits, so its size is $O(m\log m)$. The verifier checks range, uniqueness, and $m$ required edges. With an adjacency matrix, each edge lookup is constant-time under the conventional indexed model; with a TM-level encoding, the total remains polynomial. A malformed or repeated vertex causes rejection.

SAT example. For a Boolean formula $\varphi$ with variables $z_1,\ldots,z_m$, guess $m$ bits and evaluate the syntax tree bottom-up. Completeness: a satisfiable formula has an accepting assignment branch. Soundness: if any branch accepts, its bits define a satisfying assignment. This is existential semantics, not a randomized search claim.

Nondeterministic padding

For

the same length conversion used for deterministic classes applies to $\mathrm{NTIME}$ and $\mathrm{NSPACE}$. If $L$ has a nondeterministic $2^{O(n)}$-time decider and $p(n)=2^{\Theta(n)}$, its correctly padded version has a polynomial-time nondeterministic decider in total length $N=p(n)$.

The machine must first verify padding format, recover $x$, and then simulate the original NTM. Every simulated branch must meet the translated bound. Padding changes the represented language; it does not imply that the original $L$ belongs to NP.

Padding often appears in conditional arguments. One assumes an equality at one resource scale, pads or unpads instances, and derives a consequence at another scale. The algebra must state both lengths and preserve the existential acceptance condition.

Common mistakes

• Requiring every branch to accept.
• Allowing exponential certificate length.
• Treating an unverified guessed object as evidence.
• Assigning probabilities to nondeterministic choices.
• Bounding only an accepting branch instead of every branch.
• Confusing branch depth with total tree size.
• Summing work space over all conceptual branches.
• Using graph search without handling repeated configurations.
• Applying a padding conclusion to the original language.

Visualization prompt

Show a branching computation tree with one accepting leaf and map its edge labels to a certificate string.

Exercises

Exercise 1 — Accept and reject semantics

Define when an NTM accepts input $x$ and when it rejects (as a decider). Prove that swapping accept and reject states need not decide $\overline L$.

Exercise 2 — Certificate as choice string

Prove that if $L\in\mathrm{NTIME}(p(n))$ then there is a deterministic polynomial verifier with certificates of length $O(p(n))$. State completeness and soundness.

Exercise 3 — Polynomial depth is not $\mathrm P$

Prove a binary machine with branches of length $n^3$ may create $2^{\Theta(n^3)}$ tree nodes, and deduce why naive deterministic simulation does not prove $\mathrm{NP}\subseteq\mathrm P$.

Exercise 4 — Nondeterministic space measure

Define $s_N(n)$ for a nondeterministic machine. Prove that “some branch uses little space” is not the definition of $\mathrm{NSPACE}$.

Exercise 5 — Savitch and $\mathrm{NPSPACE}$

State Savitch's conclusion for constructible $s(n)\ge\log n$, and deduce $\mathrm{NPSPACE}=\mathrm{PSPACE}$.

Summary

Nondeterminism is an existential quantifier over branches. Short certificates and deterministic verifiers express the same idea; full deterministic simulation is exponentially costly.

Guided practice

Task 1 — Clique verifier

Build a polynomial verifier for CLIQUE. Prove completeness, soundness, and a certificate-length bound.

Task 2 — Complement trap

Explain why swapping accept/reject leaves in a machine for $L$ need not decide $\overline L$. Relate to $\mathrm{NP}$ versus $\mathrm{coNP}$.

Task 3 — Simple path of length $k$

Describe “simple path of length $\ge k$” in three ways (NTM, verifier, tree) and prove membership in $\mathrm{NP}$. What does deterministic simulation give?

Sources

• Student-summary evidence: merged course summary, pp. 25-42; pp. 50-54 are cited only where the material overlaps with tableaux. The summary is used for course alignment, not authoritative verification.
• Course evidence: Semester A 2026 transcripts 5-6, nondeterminism and padding.
• Verification: Sipser, 3e, pp. 292-304 and 321-330.
• Verification: Arora-Barak draft, pp. 43-64 and 83-88.
• Verification: Papadimitriou, pp. 35-51 and 159-170.