Certificado (complexidade)

Na teoria da complexidade computacional, um certificado (também chamado de witness ou testemunha) é uma string que certifica a resposta a um cálculo, ou garante a relação de alguma string em um idioma. Um certificado é muitas vezes visto como um ramo de solução dentro de um processo de verificação, que é usado para verificar se um problema dá a resposta "Sim" ou "Não".

No modelo de árvore de decisão da computação, a complexidade do certificado é o número mínimo de $n$ variáveis de entrada de uma árvore de decisão que precisam ser atribuído um valor, a fim de estabelecer definitivamente o valor da função booleana $f$.

Definição

O certificado é geralmente usado para provar semi-decidibilidade da seguinte forma:

L ∈ SD se existir um predicado de duas partes R ⊆ Σ∗ × Σ∗ tal que R é computável e que para todo x ∈ Σ∗:

   x ∈ L ⇔ existe y tal que R(x, y)

e para provar NP:

L ∈ NP se existir um verificador em tempo polinomial V tal que:

   x ∈ L ⇔ existe y tal que |y| <= |x|c e V aceita (x, y)

Exemplos

 L = {<<M>, x, w> | <M> aceita x em |w| passos?}
 Mostre que L ∈ NP.
 Verificador:
   pega a string c = <M>, x, w tal que |c| <= P(|w|)
   checar se c é aceito por M em x com no máximo |w| passos
   |c| <= O(|w|3)
   se nós tivermos a descrição da maquina de Turing com  k passos o tamanho total da computação string computada é de k2
   Assim, <<M>, x, w> ∈ L ⇔ existe c <= a|w|3 tal que <<M>, x, w, c> ∈ V ∈ P

Referências

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