Prove the Two Definitions of NP Equivalent

Convert between nondeterministic polynomial time and polynomially bounded certificates.

Problem

Prove that a language $L$ is decided by a nondeterministic polynomial-time TM if and only if there are a polynomial $p$ and deterministic polynomial-time verifier $V$ such that

Track certificate length and total verification time in both directions.

Prerequisites

Know the unit definitions and how resources are measured against encoded input length. Distinguish a conditional theorem, a reduction, and an algorithm.

Hint 1

Encode one nondeterministic choice per simulated step.

Hint 2

Reject certificates that do not describe a legal accepting computation.

Hint 3

In the reverse direction, guess exactly a polynomially padded certificate, then run $V$.

Full solution

Assume first that a nondeterministic TM $N$ decides $L$ and every branch halts within $q(n)$ steps. Because the transition relation is finite, each step has at most a constant $b$ possible choices. Encode a branch by a string $y$ of $q(n)\lceil\log b\rceil$ bits, padding after early halting. Define $V(x,y)$ to simulate $N(x)$ deterministically, using successive blocks of $y$ to select transitions. Reject if a block names no legal transition, if the simulated branch rejects, or if it has not accepted by the clock.

The certificate length is $O(q(n))$, hence polynomial. A straightforward deterministic simulation of $q(n)$ steps is polynomial in $|x|+|y|$; even a polynomial model-conversion overhead remains polynomial. There is an accepting branch of $N(x)$ exactly when some choice string drives the simulation to acceptance. Therefore

Conversely, suppose $V$ and $p$ satisfy the verifier definition, with $V$ running in time $r(|x|+|y|)$. Construct an NTM $N$ that, on input $x$, nondeterministically writes a certificate of length at most $p(|x|)$ and then runs $V(x,y)$. One convenient fixed-length implementation guesses $p(n)$ symbols including a padding symbol, verifies canonical padding, and interprets the prefix as $y$. Guessing costs $O(p(n))$ and verification costs at most $r(n+p(n))$, a polynomial in $n$. Every branch halts.

If $x\in L$, a valid witness exists and one branch guesses it, so $N$ accepts. If $x\notin L$, no witness makes $V$ accept, so every branch rejects. Thus $N$ decides $L$ nondeterministically in polynomial time.

The quantifiers matter. NP requires existence of one accepting branch or certificate for yes-instances and rejection of all branches for no-instances. It does not require a unique witness, and the verifier need not find a witness. Also, the polynomial bound must be in $|x|$, not in the numerical value encoded by $x$. Finally, a verifier must halt on every pair $(x,y)$, including malformed or overlong certificates; these may simply be rejected.

Checkpoints

Check both logical directions, halting of every relevant branch, and that output length and construction time are polynomial in the encoded input length.

Common mistakes

• Using the entire computation tableau when a choice string suffices without bounding it.
• Saying a no-instance has one rejecting branch instead of all branches rejecting.
• Letting verification time be polynomial in the numeric value of the input.

Sources and verification

• Merged summary, pp. 40-42
• 2026 transcript 8
• Sipser 3e, sec. 7.3
• Arora-Barak draft, sec. 2.1
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Provenance and confidence

The exercise is an original synthesis. Confidence reflects verification of the mathematical claim against the textbook sources listed above; course sources are used only where direct coverage is identified.

Open in the visualization gallery: Nondeterministic computation tree