(1) Extras informações para a correção de uma resposta a um problema de decisão pode ser verificada rapidamente. (2) Para qualquer propriedade gráfico P e gráfico G, um certificado para G é um grafo G' tal que G tem propriedade P se e somente se G' tem a propriedade.