Certificate (complexity)

<h2 id="use-in-definitions">Use in definitions</h2>
<p>The notion of certificate is used to define <a href="/facts/Semi-decidability/17SHPMo0">semi-decidability</a>:<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> a <a href="/facts/Formal_language/crDTyP8q">formal language</a> 
  
    
      
        L
      
    
    {\displaystyle L}
  
 is semi-decidable if there is a two-place predicate <a href="/facts/Relation_(mathematics)/HjblDaMy">relation</a>
  
    
      
        R
        ⊆
        
          Σ
          
            ∗
          
        
        ×
        
          Σ
          
            ∗
          
        
      
    
    {\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}
  
 such that 
  
    
      
        R
      
    
    {\displaystyle R}
  
 is <a href="/facts/Computability/VpnJUkPN">computable</a>, and such that for all 
  
    
      
        x
        ∈
        
          Σ
          
            ∗
          
        
      
    
    {\displaystyle x\in \Sigma ^{*}}
  
:
</p>
   x ∈ L ⇔ there exists y such that R(x, y)

<p>Certificates also give definitions for some complexity classes which can alternatively be characterised in terms of <a href="/facts/Nondeterministic_Turing_machine/zv2x6XPG">nondeterministic Turing machines</a>. A language 
  
    
      
        L
      
    
    {\displaystyle L}
  
 is in <a href="/facts/NP_(complexity)/6muUfVMI">NP</a> if and only if there exists a polynomial 
  
    
      
        p
      
    
    {\displaystyle p}
  
 and a <a href="/facts/Polynomial-time/77T62gmf">polynomial-time</a> bounded <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a> 
  
    
      
        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)}
  
.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> The class <a href="/facts/Co-NP/M67JgWNa">co-NP</a> has a similar definition, except that there are certificates for the words <i>not</i> in the language.
</p><p>The class <a href="/facts/NL_(complexity)/FvNaeSaM">NL</a> 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.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> 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.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h2 id="examples">Examples</h2>
<p>The problem of determining, for a given graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 and number 
  
    
      
        k
      
    
    {\displaystyle k}
  
, if the graph contains an <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">independent set</a> 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 class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p><p>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:
</p>
 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

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Witness_(mathematics)/H4JXNTHw">Witness (mathematics)</a>, an analogous concept in mathematical logic</li></ul>

<h2 id="external-links">External links</h2>
<ul><li>Buhrman, Harry; de Wolf, Ronald (2002), <i>Complexity Measures and Decision Tree Complexity:A Survey</i>.</li>
<li><a href="http://www.cs.princeton.edu/theory/complexity/dectreechap.pdf">Computational Complexity: a Modern Approach by Sanjeev Arora and Boaz Barak</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Cook, Stephen. "Computability and Noncomputability" (PDF). Retrieved 7 February 2013. <a href="http://www.cs.toronto.edu/~sacook/csc463h/notes/comp.pdf" target="_blank">http://www.cs.toronto.edu/~sacook/csc463h/notes/comp.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Arora, Sanjeev; Barak, Boaz (2009). "Definition 2.1". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. <a href="978-0-521-42426-4" target="_blank">978-0-521-42426-4</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Arora, Sanjeev; Barak, Boaz (2009). "Definition 4.19". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. <a href="978-0-521-42426-4" target="_blank">978-0-521-42426-4</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>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. <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Arora, Sanjeev; Barak, Boaz (2009). "Example 2.2". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. <a href="978-0-521-42426-4" target="_blank">978-0-521-42426-4</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Certificate (complexity) open-in-new

Certificate (complexity)