• Images
• Videos
• Documents
• Books
• Articles

Use in definitions

The notion of certificate is used to define semi-decidability:¹ a formal language L {\displaystyle L} is semi-decidable if there is a two-place predicate relation R ⊆ Σ ∗ × Σ ∗ {\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}} such that R {\displaystyle R} is computable, and such that for all x ∈ Σ ∗ {\displaystyle x\in \Sigma ^{*}} :

x ∈ L ⇔ there exists y such that R(x, y)

Certificates also give definitions for some complexity classes which can alternatively be characterised in terms of nondeterministic Turing machines. A language L {\displaystyle L} is in NP if and only if there exists a polynomial p {\displaystyle p} and a polynomial-time bounded Turing machine M {\displaystyle M} such that every word x ∈ Σ ∗ {\displaystyle x\in \Sigma ^{*}} is in the language L {\displaystyle L} precisely if there exists a certificate c {\displaystyle c} of length at most p ( | x | ) {\displaystyle p(|x|)} such that M {\displaystyle M} accepts the pair ( x , c ) {\displaystyle (x,c)} .² The class co-NP has a similar definition, except that there are certificates for the words not in the language.

The class NL has a certificate definition: a problem in the language has a certificate of polynomial length, which can be verified by a deterministic logarithmic-space bounded Turing machine that can read each bit of the certificate once only.³ Alternatively, the deterministic logarithmic-space Turing machine in the statement above can be replaced by a bounded-error probabilistic constant-space Turing machine that is allowed to use only a constant number of random bits.⁴

Examples

The problem of determining, for a given graph G {\displaystyle G} and number k {\displaystyle k} , if the graph contains an independent set of size k {\displaystyle k} is in NP. Given a pair ( G , k ) {\displaystyle (G,k)} in the language, a certificate is a set of k {\displaystyle k} vertices which are pairwise not adjacent (and hence are an independent set of size k {\displaystyle k} ).⁵

A more general example, for the problem of determining if a given Turing machine accepts an input in a certain number of steps, is as follows:

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 k2 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

External links

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

References

1. Cook, Stephen. "Computability and Noncomputability" (PDF). Retrieved 7 February 2013. http://www.cs.toronto.edu/~sacook/csc463h/notes/comp.pdf ↩

2. Arora, Sanjeev; Barak, Boaz (2009). "Definition 2.1". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. 978-0-521-42426-4 ↩

3. Arora, Sanjeev; Barak, Boaz (2009). "Definition 4.19". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. 978-0-521-42426-4 ↩

4. A. C. Cem Say, Abuzer Yakaryılmaz, "Finite state verifiers with constant randomness," Logical Methods in Computer Science, Vol. 10(3:6)2014, pp. 1-17. ↩

5. Arora, Sanjeev; Barak, Boaz (2009). "Example 2.2". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. 978-0-521-42426-4 ↩