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".
Contents
In the decision tree model of computation, certificate complexity is the minimum number of the
Definition
Certificate is generally used to prove semi-decidability as following:
L ∈ SD iff there is a two-place predicate R ⊆ Σ∗ × Σ∗ such that R is computable, and such that for all x ∈ Σ∗:
x ∈ L ⇔ there exists y such that R(x, y)and to prove NP as following:
L ∈ NP iff there is a polytime verifier V such that:
x ∈ L ⇔ there exists y such that |y| <= |x|c and V accepts (x, y)