co-NP-completo

Na teoria da complexidade computacional, problemas computacionais co-NP-completos são os problemas mais difíceis em co-NP, no sentido de que são os mais propensos a não serem P. Se existisse uma forma de resolver um problema co-NP-completo rapidamente, então esse algoritmo poderia ser usado para resolver todos os problemas co-NP de forma rápida.

Um problema co-NP-completo é o complemento de um problema NP-completo. Existem alguns problemas que estão em NP e co-NP, contudo não se sabe se essas classes são iguais, embora a desigualdade seja o pensamento mais provável.

Fortune mostrou em 1979 que se alguma sparse language é co-NP-completa (ou apenas co-NP-difícil), então P = NP, um fundamento essencial para o Mahaney's theorem.

Definição formal

Um Problema de decisão C é co-NP-completo se está em co-NP e se qualquer problema em co-NP é reduzido em tempo polinomial a ele. Isso significa que para cada problema co-NP L, existe um algoritmo em tempo polinomial que pode transformar qualquer instância de L em uma instância de C com o mesmo valor de verdade. Como consequência, se tivermos um algoritmo em tempo polinomial para C, poderíamos resolver qualquer problema em tempo polinomial.

Exemplo

Um exemplo simples de um problema co-NP-completo é a tautologia, o problema de determinar se uma fórmula booleana é uma tautologia, isso é, se todos as possíveis combinações de valores atribuídos às variáveis produzem uma afirmação verdadeira. Isso está intimamente relacionado ao problema de satisfatibilidade booleana, que pergunta se existe ao menos uma combinação de atribuição que satisfaz a fórmula. Observe que o problema da tautologia para fórmulas booleanas positivas permanece Co-NP-completo, embora o problema da satisfatibilidade seja trivial, como cada uma das fórmulas deve ser satisfazível.