- 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.
- Buhrman, Harry; Wolf, Ronald (2002), Complexity Measures and Decision Tree Complexity:A Survey .
- Computational Complexity: a Modern Approach by Sanjeev Arora and Boaz Barak
P ≟ NP This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it.