 |
The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style. (October 2009) |
Certificate is one of the most important definitions in complexity analysis. Certificate is often thought as a solution path within verification process, which is used to check either a problem gives an answer "Yes" or "No". This is a set of sufficient conditions. A 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.
References
- Buhrman, Harry; Wolf, Ronald (2002), Complexity Measures and Decision Tree Complexity:A Survey.
- Computational Complexity: a Modern Approach by Sanjeev Arora and Boaz Barak
See also
| P ≟ NP | This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
