Certificate (complexity)

In computational complexity theory, a certificate (also called a witness) is a string that certifies the answer to a computation, or certifies the membership of some string in a language. A certificate is often thought of as a solution path within a verification process, which is used to check whether a problem gives the answer "Yes" or "No".

In the decision tree model of computation, certificate complexity is the minimum number of the ${\displaystyle n}$ input variables of a decision tree that need to be assigned a value in order to definitely establish the value of the Boolean function ${\displaystyle f}$.

The notion of certificate is used to define semi-decidability:¹ a formal language ${\displaystyle L}$ is semi-decidable if there is a two-place predicate relation${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}$ such that ${\displaystyle R}$ is computable, and such that for all ${\displaystyle x\in \Sigma ^{*}}$:

   x ∈ L ⇔ there exists y such that R(x, y)

In this definition, y is the certificate, or witness, for the membership of x in L.

Certificates also give definitions for some complexity classes which can alternatively be characterised in terms of nondeterministic Turing machines. A language ${\displaystyle L}$ is in NP if and only if there exists a polynomial ${\displaystyle p}$ and a polynomial-time bounded Turing machine ${\displaystyle M}$ such that every word ${\displaystyle x\in \Sigma ^{*}}$ is in the language ${\displaystyle L}$ precisely if there exists a certificate ${\displaystyle c}$ of length at most ${\displaystyle p(|x|)}$ such that ${\displaystyle M}$ accepts the pair ${\displaystyle (x,c)}$.² The class co-NP has a similar definition, except that there are certificates for the words not in the language.

The class NL has a certificate definition: a problem in the language has a certificate of polynomial length, which can be verified by a deterministic logarithmic-space bounded Turing machine that can read each bit of the certificate once only.³ Alternatively, the deterministic logarithmic-space Turing machine in the statement above can be replaced by a bounded-error probabilistic constant-space Turing machine that is allowed to use only a constant number of random bits.⁴

The problem of determining, for a given graph ${\displaystyle G}$ and number ${\displaystyle k}$, if the graph contains an independent set of size ${\displaystyle k}$ is in NP. Given a pair ${\displaystyle (G,k)}$ in the language, a certificate is a set of ${\displaystyle k}$ vertices which are pairwise not adjacent (and hence are an independent set of size ${\displaystyle k}$).⁵

A more general example, for the problem of determining if a given Turing machine accepts an input in a certain number of steps, is as follows:

 L = {<<M>, x, w> | does <M> accept x in |w| steps?}
 Show L ∈ NP.
 verifier:
   gets string c = <M>, x, w such that |c| <= P(|w|)
   check if c is an accepting computation of M on x with at most |w| steps
   |c| <= O(|w|3)
   if we have a computation of a TM with k steps the total size of the computation string is k2
   Thus, <<M>, x, w> ∈ L ⇔ there exists c <= a|w|3 such that <<M>, x, w, c> ∈ V ∈ P