Qual é a diferença entre NP e co-NP

Quando você quer provar a dificuldade de um problema, você tem que transformá-lo em algo chamado de problema de decisão, o que significa um problema de tipo de resposta "sim/não". Por exemplo, em Set Cover, podemos perguntar " podemos cobrir todos os elementos usando apenas subconjuntos X?" onde X é um número arbitrário. Nós podemos mostrar que este problema existe em NP porque uma solução para ele é facilmente verificável; você fornece os subconjuntos X, e eu verifico para ver se todos os elementos são cobertos em tempo polinomial. Se pudermos resposta eficiente responder " sim " para o problema de decisão, então podemos minimizar X e, assim, resolver o problema de Cobertura Conjunto de forma eficiente (provando assim P=NP).

O Co - * (Co-NP, Co-NP-completo) concentra-se em responder "não" ao problema de decisão complementado. Por exemplo, o problema de decisão complementado da cobertura de Conjuntos seria "para cada combinação de subconjuntos X, é impossível cobrir todos os elementos?"[[3] Responder "não" a esta pergunta requer que você forneça um contra-exemplo.

Em resumo: NP está preocupado com uma resposta" sim " para algum problema de decisão. Co-NP está preocupado com uma resposta" não " para o mesmo, mas complementado, problema de decisão.