Co-NP
Na Teoria da complexidade, co-NP é uma Classe de complexidade. Um problema formula_1 é membro de co-NP se e somente se seu complemento formula_2 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.
Q5157286
Teoria da complexidade
Concept
Q908207
Classe de complexidade
Concept
Q628036
NP
MISC
Q215206
NP-Completo
MISC
Q1154420
Problema da soma dos subconjuntos
Concept
Q1142354
co-NP-completo
EVE
Q1190223
Máquina de Turing não determinística
Concept
Q4846249
Fatoração de inteiros
Concept
Q4846249
Fatoração de inteiros
Concept
Q49008
primariedade
Concept
Q294284
Teste de primalidade AKS
Concept
Q955748
Co-NP
MISC
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+2002^^http://www.w3.org/2001/XMLSchema#decimal
2002
NUMBER
instance of
has quality