Certificate (complexity)

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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 $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 $f$ .

Use in definitions

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

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

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\in \Sigma ^{*}$ 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)$ .^[2] 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.^[3] 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.^[4]

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$ ).^[5]

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|³)
   if we have a computation of a TM with k steps the total size of the computation string is k²
   Thus, <<M>, x, w> ∈ L ⇔ there exists c <= a|w|³ such that <<M>, x, w, c> ∈ V ∈ P

References

^ Cook, Stephen. "Computability and Noncomputability" (PDF). Retrieved 7 February 2013.
^ Arora, Sanjeev; Barak, Boaz (2009). "Definition 2.1". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
^ Arora, Sanjeev; Barak, Boaz (2009). "Definition 4.19". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
^ A. C. Cem Say, Abuzer Yakaryılmaz, "Finite state verifiers with constant randomness," Logical Methods in Computer Science, Vol. 10(3:6)2014, pp. 1-17.
^ Arora, Sanjeev; Barak, Boaz (2009). "Example 2.2". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

External links

Buhrman, Harry; de Wolf, Ronald (2002), Complexity Measures and Decision Tree Complexity:A Survey.
Computational Complexity: a Modern Approach by Sanjeev Arora and Boaz Barak

[1] Cook, Stephen. "Computability and Noncomputability" (PDF). Retrieved 7 February 2013.

[2] Arora, Sanjeev; Barak, Boaz (2009). "Definition 2.1". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

[3] Arora, Sanjeev; Barak, Boaz (2009). "Definition 4.19". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

[4] A. C. Cem Say, Abuzer Yakaryılmaz, "Finite state verifiers with constant randomness," Logical Methods in Computer Science, Vol. 10(3:6)2014, pp. 1-17.

[5] Arora, Sanjeev; Barak, Boaz (2009). "Example 2.2". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

[1]

[2]

[3]

[4]

[5]

Use in definitions

Examples

See also

References

External links