Co-NP

Na Teoria da complexidade, co-NP é uma Classe de complexidade. Um problema ${\mathcal {X}}$ é membro de co-NP se e somente se seu complemento ${\overline {\mathcal {X}}}$ esta na classe de complexidade NP. Em outras palavras, co-NP é a classe de problemas para qual existe a prova, de forma eficiente, para não existência de instância, os chamados contra-exemplos.

Um exemplo de um problema NP-Completo é o Problema da soma dos subconjuntos: dado um conjunto finito de números inteiros, existe um subconjunto não vazio cuja soma é zero? Para dar a prova de que existe uma instância, primeiro é necessário especificar um subconjunto não vazio que tenha como soma zero. O problema complementar esta em co-NP e pergunta: "dado um conjunto finito de inteiros, cada um dos subconjuntos não tem soma zero?". Para provar a não existência de uma instância você precisa especificar um subconjunto não vazio que tenha soma zero, que é facilmente verificável. P, a classe dos problemas resolvíveis em tempo polinomial, é um subconjunto de tanto NP quanto co-NP. P é considerado estritamente um subconjunto de ambas classes (e comprovadamente não pode ser rigoroso em um caso, e não em outro). NP e co-NP são também considerados iguais. Caso seja, então um problema que não seja NP-completo pode ser NP e um problema que não seja co-NP-completo pode ser NP.

Isso pode ser demonstrado como se segue. Assumindo que existe um problema NP-completo que esta em co-NP. Já que todos os problemas em NP podem ser reduzidos para esse problemas, então para todos os problemas em NP nos podemos construir a Máquina de Turing não determinística que decide o complemento desse problema em tempo polinomial,ou seja, NP é um subconjunto de co-NP. Visto que o conjunto de complementos dos problemas NP é subconjunto do conjunto de complementos dos problemas em co-NO, ou seja, co-NP é um subconjunto de NO.Uma vez que já sabia que NP é subconjunto de co-NP, então eles são iguais. A prova para o fato de que nenhum problema co-NP-completo pode ser em NP é simétrica.

Se um problema pode ser apresentado com sendo tanto em NP quanto em co-NP, isso serve de evidência de que esse problema provavelmente não é NP-completo,caso contrário NP = co-NP.

Um exemplo de problema que sabe-se estar em NP e em co-NP é a Fatoração de inteiros: dado números inteiros positivos m e n determine se m tem um fator menor que n e maior que um. A participação em NP é clase; se m tem um fator, entao o fator é a prova. Participação em co-NP é mais sutil; primeiro é preciso lista os fatores primos de m e fornecer uma certificado de primariedade para cada um.

Fatoração de inteiros é muitas vezes confundido com o problema da primariedade. Ambos testes de primariedade e fatoração são conhecidos como problemas No e Co-NP. O Teste de primalidade AKS, publicado em 2002, prova que o teste de primariedade também esta em P, enquanto que fatoração pode ou não ter um algoritmo em tempo polinomial.