Certificate (complexity)

From Wikipedia, the free encyclopedia

Please help improve this article or section by expanding it.
Further information might be found on the talk page or at requests for expansion. (March 2008)

This article does not cite any references or sources. (December 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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.