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

## Contents

* 1 Use in definitions
* 2 Examples
* 3 See also
* 4 References
* 5 External links

## 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 ⊆ Σ∗ × Σ∗ such that R is computable, and such that for all x ∈ Σ∗:

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 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|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

## See also

* Witness (mathematics), an analogous concept in mathematical logic

## References

1. ↑ Cook, Stephen. "Computability and Noncomputability". http://www.cs.toronto.edu/~sacook/csc463h/notes/comp.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. http://www.cs.princeton.edu/theory/complexity/.
3. ↑ Arora, Sanjeev; Barak, Boaz (2009). "Definition 4.19". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. http://www.cs.princeton.edu/theory/complexity/.
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. http://www.cs.princeton.edu/theory/complexity/.

## 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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Certificate (complexity). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Certificate_(complexity)&oldid=198734"