Problèmes décidables pas dans NP

Re: Problèmes décidables pas dans NP

by Jean-Cédric Chappelier -
Number of replies: 0

Hmm... pas forcément car c'est un peu plus compliqué « que ça » et est de toutes façons totalement hors du cours (c'est la partie supérieure du diagramme des complexités des problèmes, entre NP et non-décidables, que l'on a laisser blanche/vide).

Au niveau du cours (et pour répondre à la question 2 2017), il suffit de savoir la définition de NP, dont la proposition B est la négation.

Pour aller plus loin : je ne suis pas sûr (et cela sort de mon domaine de compétence) que l'on puisse affirmer ce que vous dites car, à ma connaissance, l’existence de problèmes de décision strictement hors de NP est conditionnée par des suppositions du genre  (différentes mais similaires à) « P différent de NP » dont on ne connaît pas la réponse (p.ex. est-ce que NP = PSPACE). Ce sont donc des résultats plutôt indirects. Et donc, je doute que l'on puisse vraiment conclure dans tous les cas (sinon, j'ai bien l'impression que l'on pourrait conclure, p.ex. sur NP et PSPACE).

Dans ce genre de questions, il faut toujours faire très attention à ce que l'on affirme... Comme par exemple, pour en revenir au niveau du cours : on ne peut pas dire « dans NP mais pas dans P » ;-) (car on ne sait pas si cela existe)