Bonjour,
Je me demande si on sait vérifier une solution pour tous les problems décidables et est-ce qu'on sait aussi dans quel temps? Par la question 2 de l'examen 2017 on sait qu' un problème qui n'est pas dans NP prend un temps plus que polynomial pour vérifier une solution. Donc, on serait pour tous problèmes décidables dans quel temps on peut vérifier une solution?
Merci
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)