34.2-8

Mostre que TAUTOLOGY ∈ co-NP.

Vamos mostrar que seu complemento, que chamaremos de co-TAUTOLOGY, está em NP. Uma atribuição de 0 e 1 às variáveis de uma fórmula que façam com que a fórmula resulte em 0 é um certificado de que a fórmula pertence a co-TAUTOLOGY, e pode ser verificado em tempo polinomial. Isto mostra que co-TAUTOLOGY ∈ NP, e portanto TAUTOLOGY ∈ co-NP.