Certificate (Complexity Theory)

Definition

Certificate (Complexity Theory)

Let $L\subseteq {\Sigma }^{\ast }$ be the language of positive problem instances of a decision problem, with instances encoded as strings. A certificate relation for $L$ is a relation

$$R\subseteq {\Sigma }^{\ast }\times {\Sigma }^{\ast }$$

such that

$$x\in L⟺\exists y\in {\Sigma }^{\ast }:(x,y)\in R.$$

A string $y$ satisfying $(x,y)\in R$ is a certificate for the positive instance $x$. The relation identifies which candidates certify which instances; the definition itself imposes no bound on the length of $y$ and no efficiency requirement on deciding membership in $R$.

NP Certificates

For NP, certificates must satisfy both restrictions:

$$x\in L⟺\exists y\in {\Sigma }^{\ast }:(|y|\le p(|x|)\wedge V(x,y)=1),$$

where $p$ is a polynomial and $V$ is a polynomial-time verifier. Equivalently, the certificate relation is polynomially balanced and polynomially decidable. Thus, an NP certificate is a polynomially bounded, efficiently verifiable certificate; the word certificate itself is more general.