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

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top