Co-NP
Na Teoria da complexidade, co-NP é uma Classe de complexidade. Um problema X{displaystyle {mathcal {X}}}
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.[1]
Referências
↑
Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781-793.
