Certificate (complexity)

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style.

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.

[edit] 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

[edit] See also

• P = NP problem

This computer science article is a stub. You can help Wikipedia by expanding it.