Co-NP

Na teoria da complexidade computacional, co-NP é uma classe de complexidade. Um problema de decisão X é membro de co-NP se e somente se seu complemento X está na classe de complexidade NP. A classe pode ser definida da seguinte forma: um problema de decisão está em co-NP precisamente se apenas nenhuma instância tiver um "certificado" e há um algoritmo de tempo polinomial que pode ser usado para verificar qualquer suposto certificado.

Isso é, co-NP é o conjunto de problemas de decisão onde existe um polinomial p(n)(n)} e uma máquina de Turing limitada em tempo polinomial M tal que para cada instância x, x é um Não.-instância se e somente se: para algum certificado possível c de comprimento limitado por p(n)(n)}, a máquina de Turing M aceita o par (x, c).

Problemas Complementares

Enquanto um problema NP pergunta se uma determinada instância é uma instância sim, seu complemento pergunta se uma instância é uma instância não, o que significa que o complemento está em co-NP. Qualquer instância sim para o problema NP original torna-se uma instância não para seu complemento e vice-versa.

Insatisfabilidade

Um exemplo de um problema NP-completo é o problema de satisfatibilidade booleana: dada uma fórmula booleana, ela é satisfatória (existe uma entrada possível para a qual a fórmula retorna verdadeira)? O problema complementar pergunta: "dada uma fórmula booleana, ela é insatisfatível (todas as entradas possíveis para a saída da fórmula são falsas)?". Uma vez que este é o complemento do problema de satisfatibilidade, um certificado para uma instância não é o mesmo que para uma instância sim do original Problema NP: um conjunto de atribuições de variáveis booleanas que tornam a fórmula verdadeira. Por outro lado, um certificado de instância sim para o problema complementar seria tão complexo quanto a instância não do problema de satisfatibilidade NP original.

Problemas duplos

Co-NP-completude

Um problema L é co-NP-completo se e somente se L está em co-NP e para qualquer problema em co-NP, existe um polinômio redução de tempo desse problema para L.

Redução de Tautologia

Determinar se uma fórmula na lógica proposicional é uma tautologia é co-NP-completo: isto é, se a fórmula for avaliada como verdadeira em todas as atribuições possíveis para suas variáveis.

Relação com outras classes

Inclusões de classes de complexidade, incluindo P, NP, co-NP, BPP, P/poli, PH e PSPACE

P, a classe de problemas solucionáveis em tempo polinomial, é um subconjunto de NP e co-NP. P é considerado um subconjunto estrito em ambos os casos (e comprovadamente não pode ser estrito em um caso e não estrito no outro).

NP e co-NP também são considerados desiguais. Se assim for, então nenhum problema NP-completo pode estar em co-NP e nenhum problema co-NP-completo pode estar em NP. Isso pode ser mostrado da seguinte forma. Suponha para o bem da contradição existe um problema NP-completo X que está no co-NP. Uma vez que todos os problemas em NP podem ser reduzidos a X, segue-se que para cada problema em NP, podemos construir uma máquina de Turing não determinística que decide seu complemento em tempo polinomial; i.e., PN⊆ ⊆ co-NP{displaystyle {textsf {NP}}subseteq {textsf {co-NP}}}. A partir disso, segue-se que o conjunto de complementos dos problemas em NP é um subconjunto do conjunto de complementos dos problemas no co-NP; isto é, co-NP⊆ ⊆ PN{displaystyle {textsf {co-NP}}subseteq {textsf {NP}}}. Assim co-NP= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =PN{displaystyle {textsf {co-NP}}={textsf (NP). A prova de que nenhum problema co-NP-completo pode estar em NP se PN≠ ≠ co-NP{displaystyle {textsf {NP}}neq {textsf {co-NP}}} é simétrica.

co-NP é um subconjunto de PH, que por sua vez é um subconjunto de PSPACE.

Fatoração inteira

Um exemplo de um problema que é conhecido por pertencer tanto a NP quanto a co-NP (mas não conhecido por estar em P) é a fatoração de inteiros: dados inteiros positivos m e n, determine se m tem um fator menor que n e maior que um. A adesão ao NP é clara; se m tiver tal fator, então o próprio fator é um certificado. A associação em co-NP também é direta: pode-se apenas listar os fatores primos de m, todos maiores ou iguais a n, que o verificador pode confirmar como válidos por multiplicação e o teste de primalidade AKS. Atualmente, não se sabe se existe um algoritmo de tempo polinomial para fatoração, equivalentemente se a fatoração inteira está em P e, portanto, este exemplo é interessante como um dos problemas mais naturais conhecidos por estar em NP e co-NP, mas não conhecido por estar em P.