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 formula_1 input variables of a decision tree that need to be assigned a value in order to definitely establish the value of the Boolean function  formula_2. Use in definitions. The notion of certificate is used to define semi-decidability: "L" is semi-decidable if there is a two-place predicate R ⊆ Σ∗ × Σ∗ such that R is computable, and such that for all x ∈ Σ∗: Certificates also give definitions for some complexity classes which can alternatively be characterised in terms of nondeterministic Turing machines. A language "L" is in NP if and only if there exists a polynomial "p" and a polynomial-time bounded Turing machine "M" such that every word "x" is in the language "L" precisely if there exists a  certificate "c" of length at most "p(|x|)" such that "M" accepts the pair ("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. Examples. The problem of determining, for a given graph "G" and number "k", if the graph contains an independent set of size "k" is in NP. Given a pair ("G", "k") in the language, a certificate is a set of "k" vertices which are pairwise not adjacent (and hence are an independent set of size "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: