Certificate (complexity)
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 .
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 .
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: L = { , x, w> | does accept x in |w| steps?} Show L ∈ NP. verifier: gets string c = , x, w such that |c| 3 ) if we have a computation of a TM with k steps the total size of the computation string is k 2 Thus, , x, w> ∈ L ⇔ there exists c 3 such that , x, w, c> ∈ V ∈ P
See also
Witness (mathematics), an analogous concept in mathematical logic
References
External links
. Computational Complexity: a Modern Approach by Sanjeev Arora and Boaz Barak
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373800333 under CC BY-SA 4.0; modifications have been made.