Polynomial-time verifiers with polynomially bounded certificates

Fix the binary pairing $⟨x,u⟩:=1^{\mathrm{\mid }x\mathrm{\mid }}0xu$ for binary words $x,u\in \{0,1{\}}^{\ast }$. Let $L\subseteq \{0,1{\}}^{\ast }$ be a language. A polynomial-time verifier with polynomially bounded certificates for $L$ consists of:

• a binary relation $R\subseteq \{0,1{\}}^{\ast }\times \{0,1{\}}^{\ast }$ whose paired language $L_R:=\{⟨x,u⟩:(x,u)\in R\}$ belongs to $P$, and
• a polynomial $p$ such that $x\in L⟺\mathrm{\exists }u\in \{0,1{\}}^{\ast }\text{ with }\mathrm{\mid }u\mathrm{\mid }\le p(\mathrm{\mid }x\mathrm{\mid })\text{ and }(x,u)\in R\mathrm{.}$

Any such $u$ is called a certificate or witness for $x$.

• The verifier checks a paired instance $(x,u)$ in polynomial time, while the polynomial $p$ bounds how long a successful certificate ever needs to be.

• Allowing the empty certificate is legitimate; that corresponds to the case $u=\epsilon$.