Co-NP

Na Teoria da complexidade, co-NP é uma Classe de complexidade. Um problema X {\displaystyle {\mathcal {X}}} é membro de co-NP se e somente se seu complemento X ¯ {\displaystyle {\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...