The verifier and nondeterministic definitions of NP agree

Assume item 1. By [L1], choose a verifier relation $R$ and a polynomial certificate bound $p$. Let $D_R$ be a deterministic polynomial-time decider for the paired language $L_R=\{⟨x,u⟩:(x,u)\in R\}$. Build a nondeterministic machine $N$ that, on input $x$, first guesses a binary word $u$ of length at most $p(\mathrm{\mid }x\mathrm{\mid })$ and then runs $D_R$ on $⟨x,u⟩$, accepting exactly when $D_R$ accepts. Because every branch chooses at most $p(\mathrm{\mid }x\mathrm{\mid })$ guessed bits and then performs one polynomial-time deterministic verification, every branch halts within polynomial time. Since $x\in L$ exactly when some certificate $u$ makes $(x,u)\in R$, the machine $N$ accepts exactly the words of $L$. Thus item 2 holds.

Assume item 2. By [L2], fix a nondeterministic machine $N$ and an exponent $k$ such that every branch on inputs of length $n$ halts within $c{n}^k$ steps for some constant $c$. Let $b$ be the maximum number of available nondeterministic choices in any one local configuration of $N$, and choose an integer $r\ge 1$ with $2^r\ge b$. An accepting branch is then determined by a finite sequence $d_1,\dots ,d_t$ of at most $c{n}^k$ choice numbers from $\{0,\dots ,b-1\}$. Encode that sequence as the binary word $u:=1^{t}0{\beta }_1\cdots {\beta }_t,$ where each ${\beta }_i$ is the $r$-bit binary expansion of $d_i$. The initial unary header recovers $t$, and then the decoder reads exactly $t$ consecutive blocks of length $r$, so this branch description is effectively decodable.

Define a deterministic verifier for $L$ as follows. On input $⟨x,u⟩$, first decode $u$ by reading its unary header and then the declared number of $r$-bit choice blocks; reject malformed encodings. Next simulate $N$ on $x$ while forcing those choices in order, reject if the certificate requests a nonexistent choice or ends before acceptance, and accept exactly when the forced run ends in an accepting state after consuming the full encoded branch description. Step 1.2 guarantees that $x\in L$ yields some accepting-branch certificate, and any accepting certificate describes a genuine accepting branch. The certificate length is polynomial in $\mathrm{\mid }x\mathrm{\mid }$ because it has one unary header bit per simulated choice and each choice uses the fixed block length $r$, with at most $c{n}^k$ choices. The verifier runtime is therefore polynomial in $\mathrm{\mid }x\mathrm{\mid }+\mathrm{\mid }u\mathrm{\mid }$ because it only decodes $u$ and replays that many steps of $N$. Therefore item 1 holds by [L1].

Steps 1.1 and 2.1 prove both directions, so the verifier and nondeterministic definitions of NP agree. The lower bound in [L3] is compatible with these polynomial bounds: reading the whole input and certificate is already only linear in their lengths.