[proofplan] We prove both implications by translating between nondeterministic choices and deterministic certificates. From a nondeterministic polynomial-time machine, we encode an accepting computation branch as a polynomial-length certificate and let a deterministic verifier replay the branch. Conversely, from a polynomial-time verifier, we build a nondeterministic machine that guesses the polynomially bounded certificate and then runs the verifier. [/proofplan] [step:Encode accepting nondeterministic branches as polynomial-length certificates] Assume that $L$ is accepted by a nondeterministic Turing machine $N$ whose every computation branch on input $x \in \Sigma^*$ halts within $p(|x|)$ steps, where $p:\mathbb{N}\to\mathbb{N}$ is a polynomial. Because $N$ has finitely many states, tape symbols, and transition rules, there is a number $b \in \mathbb{N}$ such that at every configuration of $N$ there are at most $b$ legal nondeterministic transitions. If $b=0$, then $N$ has no accepting branches, so $L=\varnothing$, and the verifier that always rejects proves the verifier condition with certificate bound $q(n)=0$. Hence assume $b\geq 1$. Fix once and for all a binary encoding of each choice number in $\{1,\dots,b\}$ using words of length \begin{align*} \ell := \max\{1,\lceil \log_2 b\rceil\}. \end{align*} A computation branch of $N$ of length at most $p(|x|)$ is therefore encoded by a binary string $c \in \{0,1\}^*$ of length at most \begin{align*} \ell p(|x|). \end{align*} The intended meaning of $c$ is that its consecutive blocks of length $\ell$ prescribe which legal transition of $N$ should be taken at each nondeterministic step. [guided] We need to turn the existential nature of nondeterminism into an existentially quantified certificate. The only information needed to specify one computation branch of $N$ is the list of choices made along that branch. Since $N$ is a fixed machine, it has only finitely many possible transition rules. Therefore there is a fixed number $b \in \mathbb{N}$ such that no configuration has more than $b$ legal outgoing transitions. If $b=0$, then no branch can ever move to an accepting computation, so the accepted language is empty. In that degenerate case, the deterministic verifier that rejects every input witnesses the verifier characterization with certificate bound $q(n)=0$. Assume now that $b\geq 1$. We encode each possible choice number in $\{1,\dots,b\}$ by a binary word of length \begin{align*} \ell := \max\{1,\lceil \log_2 b\rceil\}. \end{align*} This length is constant because $N$ is fixed; it does not depend on the input $x$. A branch on input $x$ has at most $p(|x|)$ steps by hypothesis. Thus the entire branch can be described by at most $p(|x|)$ many choice blocks, each of length $\ell$, so the certificate length is bounded by \begin{align*} \ell p(|x|). \end{align*} This is polynomial in $|x|$ because $\ell$ is a constant and $p$ is a polynomial. The certificate is not claiming that the branch accepts by itself; it only supplies the choices. The verifier will still check legality of each chosen transition and will accept only if the simulated branch reaches an accepting state. [/guided] [/step] [step:Build a deterministic verifier by replaying the encoded branch] Define a deterministic Turing machine $V$ as follows. On input $(x,c) \in \Sigma^* \times \{0,1\}^*$, the machine $V$ simulates $N$ on input $x$. At the $t$-th simulated nondeterministic step, where $t \in \{1,\dots,p(|x|)\}$, the machine reads the $t$-th block of length $\ell$ from $c$, interprets that block as a choice number in $\{1,\dots,b\}$, checks whether that numbered transition is legal in the current simulated configuration, and follows it if it is legal. If the block is missing, malformed, or names an illegal transition, then $V$ rejects. If the simulated branch reaches an accepting state, then $V$ accepts; if the simulated branch halts without accepting, then $V$ rejects. The simulation performs at most $p(|x|)$ simulated steps. Each simulated step can be carried out in time polynomial in $|x|+|c|$ because $N$ is fixed and its configurations have length at most polynomial in the simulated time. Hence there is a polynomial $r:\mathbb{N}\to\mathbb{N}$ such that $V$ halts on every input $(x,c)$ within $r(|x|+|c|)$ steps. Let \begin{align*} q(n) := \ell p(n). \end{align*} If $x \in L$, then by definition of acceptance by $N$ there is an accepting branch of $N$ on $x$. Encoding the choices along that branch gives a certificate $c \in \{0,1\}^*$ with $|c|\leq q(|x|)$, and the verifier accepts $(x,c)$ because its simulation exactly follows that accepting branch. Conversely, if there is a certificate $c \in \{0,1\}^*$ with $|c|\leq q(|x|)$ such that $V$ accepts $(x,c)$, then the accepting simulation performed by $V$ is a legal accepting branch of $N$ on input $x$. Therefore $x\in L$. [/step] [step:Guess a bounded certificate nondeterministically and run the verifier] Conversely, suppose that there are a deterministic Turing machine $V$ and polynomials $q,r:\mathbb{N}\to\mathbb{N}$ satisfying the verifier condition in the statement. Construct a nondeterministic Turing machine $N$ as follows. On input $x \in \Sigma^*$, the machine nondeterministically chooses a binary string $c \in \{0,1\}^*$ of length at most $q(|x|)$, then simulates $V$ on $(x,c)$, and accepts exactly when $V$ accepts. The guessing phase takes at most $q(|x|)$ nondeterministic steps up to a fixed constant factor depending only on the machine model. After the guess, the verifier simulation takes at most \begin{align*} r(|x|+|c|) \end{align*} steps. Since $|c|\leq q(|x|)$, this is bounded by \begin{align*} r(|x|+q(|x|)). \end{align*} Thus the total running time of $N$ is bounded by a polynomial in $|x|$, namely a fixed machine-model constant times $q(|x|)$ plus $r(|x|+q(|x|))$. For correctness, if $x\in L$, then the verifier condition gives a certificate $c \in \{0,1\}^*$ with $|c|\leq q(|x|)$ such that $V$ accepts $(x,c)$. One nondeterministic branch of $N$ guesses exactly this $c$, runs $V$, and accepts. If $N$ accepts $x$, then some branch guessed a string $c$ with $|c|\leq q(|x|)$ and observed that $V$ accepts $(x,c)$; by the verifier condition, this implies $x\in L$. [/step] [step:Conclude the equivalence] The first construction shows that every language accepted by a nondeterministic polynomial-time Turing machine has a polynomial-time verifier with polynomially bounded certificates. The second construction shows that every language with such a verifier is accepted by a nondeterministic polynomial-time Turing machine. Therefore the two definitions are equivalent. [/step]