Na informática teórica , mais precisamente na teoria da complexidade dos algoritmos , um certificado é, de forma simplificada, uma informação que permite atestar que a entrada está correta.
Dado um problema de decisão , um certificado é a informação que é adicionada a um dado do problema, para certificar (no sentido de que a verificação se torna "fácil"), que a resposta ao problema para esses dados é "sim" ou "não "
Em particular, um problema de decisão está na classe NP se existe para cada dado com resposta positiva um certificado polinomial , isto é, se existe para cada dado para o qual a resposta é “sim”, um certificado de comprimento polinomial em o tamanho dos dados, de forma que a verificação da resposta para os dados fornecidos com seu certificado seja realizada em tempo polinomial .