Maintenant, je reviens au P vs NP problème.
En termes courants, P (Polynomial) désigne une classe de problèmes faciles à résoudre par l’ordinateur, c'est-à-dire qu'il existe un algorithme en temps polynomial, comme la recherche du plus court chemin entre deux endroits dans le GPS.
NP (Non-deterministic Polynomial) désigne une classe de problèmes difficiles résoudre par l’ordinateur, tels que les trois exemples dans la vidéo 【1】: le problème de 3-coloration, le problème du sac à dos, le problème SAT.
Jusqu’à présent, on n’a que des algorithmes exacts du type de la recherche par force brute en temps exponentiel, ou des algorithmes approchés en temps polynomial.
En sens commun, on sait bien que NP et P sont différents, mais lorsqu’on souhaite d’avoir une compréhension plus poussée sur NP, la théorie en informatique dit :
- Un problème dans NP est un problème dont la solution peut être rapidement vérifiable.
- Lorsqu’une solution à un problème est rapidement vérifiable (NP), peut-elle être rapidement trouvée?
Par exemple pour le problème 3-coloration, en tant donné une coloration du graphe, cette coloration peut rapidement être vérifiée si deux noeuds adjacents sont colorés de la même couleur.
Bien entendu, P est également rapidement vérifiable。 Maintenant le fameux problème P vs NP est posé ainsi 【2】:
Comment pensez-vous de cette question, c’est-à-dire, la façon de poser la question?
Référence:
【2】May 2, 2013 (The New Yorker)，A Most Profound Math Problem， Alexander Nazaryan, http://www.newyorker.com/tech/elements/a-most-profound-math-problem
Aucun commentaire:
Enregistrer un commentaire