Nécessité de définir le CO-NP en premier lieu?
-
05-11-2019 - |
Question
J'ai récemment commencé à gérer la théorie de la complexité et j'essaie de comprendre toutes les définitions et pourquoi elles ont du sens.
Une chose que je ne comprends pas très bien, c'est l'importance / la nécessité du CO-NP comme son propre ensemble / classe de problèmes. Il ne pourrait pas par exemple être tendu comme un problème NP-complete tout comme SAT ou y a-t-il une motivation spécifique pour ne pas faire de compléments d'un problème dans le même ensemble que le problème lui-même?
Je suis désolé si cela a été posé avant ou si ma question est idiote et n'a pas de sens du tout (dans ce cas, j'aimerais savoir pourquoi si possible), j'ai vraiment essayé de le rechercher à l'avance l'Internet.
Sincères amitiés,
Pas de solution correcte