Pour rappel les Problème_NP-complet sont des problèmes dont on peut vérifier si une solution au problème est valide ou non en un temps polynomial
Non.
Pour préciser, il a en fait donné la définition d'un problème NP, pas NP-complet. Pour que le problème soit NP-complet, il faut qu'il soit également NP-dur, c'est-à-dire que tu puisses ramener n'importe quel autre problème NP à celui-ci en temps polynomial.
Un problème NP-Complet appartient à la classe NP, donc on peut affirmer qu'on peut les résoudre en temps polynomial de manière non-déterministe.
Il ne dit pas le contraire : si tu peux vérifier en temps polynomial de manière déterministe, alors tu peux résoudre en temps polynomial de manière non-déterministe. Il suffit de tirer au hasard la bonne solution et de la vérifier. Mais ça, c'est pour NP.
Pour certain, on sait qu'on peut les résoudre en temps polynomial de manière déterministe (ceux qui appartiennent à P)
En effet, certains problèmes de NP appartiennent aussi à P.
mais pas tous. Et plus précisément dans le cas des problèmes NP-Complet on ne sait pas faire.
Mais le point vraiment essentiel, c'est que si un ordinateur ne sait pas le faire, on ne sait pas le faire non plus (du moins, certainement pas plus vite que lui).
[^] # Re: non
Posté par MrLapinot (site web personnel) . En réponse au journal CAPTCHA. Évalué à 3.
Pour préciser, il a en fait donné la définition d'un problème NP, pas NP-complet. Pour que le problème soit NP-complet, il faut qu'il soit également NP-dur, c'est-à-dire que tu puisses ramener n'importe quel autre problème NP à celui-ci en temps polynomial.
Il ne dit pas le contraire : si tu peux vérifier en temps polynomial de manière déterministe, alors tu peux résoudre en temps polynomial de manière non-déterministe. Il suffit de tirer au hasard la bonne solution et de la vérifier. Mais ça, c'est pour NP.
En effet, certains problèmes de NP appartiennent aussi à P.
Mais le point vraiment essentiel, c'est que si un ordinateur ne sait pas le faire, on ne sait pas le faire non plus (du moins, certainement pas plus vite que lui).