# 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 input variables of a decision tree that need to be assigned a value in order to definitely establish the value of the Boolean function .

## Definition

Certificate is generally used to prove semi-decidability as following:^{[1]}

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)

## Example

L = {<<M>, x, w> | does <M> accept x in |w| steps?} Show L ∈ NP.verifier:gets string c = <M>, x, w such that |c| <= P(|w|) check if c is an accepting computation of M on x with at most |w| steps |c| <= O(|w|^{3}) if we have a computation of a TM with k steps the total size of the computation string is k^{2}Thus, <<M>, x, w> ∈ L ⇔ there exists c <= a|w|^{3}such that <<M>, x, w, c> ∈ V ∈ P

## See also

- Witness (mathematics), an analogous concept in mathematical logic

## References

- ↑ Cook, Stephen. "Computability and Noncomputability" (PDF). Retrieved 7 February 2013.

## External links

- Buhrman, Harry; Wolf, Ronald (2002),
*Complexity Measures and Decision Tree Complexity:A Survey*. - Computational Complexity: a Modern Approach by Sanjeev Arora and Boaz Barak