← Unknownpedia : voir sur la carte
Vérifier une solution est-il aussi difficile que la trouver ?
C'est le problème « P contre NP », la question centrale de la théorie de la complexité.
Brouillon rédigé avec une IA (Claude). Les références existent, vérifiées dans OpenAlex ; le texte n’a pas encore été relu par un spécialiste. Qui écrit quoi
Ce qu'on sait
- Un problème est dans P si un ordinateur peut le résoudre en un temps raisonnable, même quand les données grossissent. Il est dans NP si, quand on vous propose une solution, vous pouvez la vérifier vite.
- Tout problème de P est dans NP : ce qu'on sait résoudre vite, on sait le vérifier vite.
- Des milliers de problèmes utiles sont dans NP (organiser des tournées, remplir un emploi du temps, ranger des objets dans le moins de boîtes), et pour beaucoup d'entre eux personne ne connaît d'algorithme rapide.
- La plupart des spécialistes pensent que P est différent de NP, sans l'avoir prouvé.
Ce qu'on ignore
- Si P est égal à NP ou non. Personne n'a démontré l'un ni l'autre. L'institut Clay offre un million de dollars à qui y parviendra : c'est un des problèmes du prix du millénaire.
Pourquoi c'est dur
- Prouver qu'un problème est impossible à résoudre vite oblige à raisonner sur tous les programmes possibles, y compris ceux que personne n'a encore imaginés.
- Des résultats montrent que plusieurs familles de techniques de preuve ne peuvent pas suffire à trancher. Il faut donc inventer de nouvelles méthodes.
Pourquoi ça compte
Si P était égal à NP avec un algorithme pratique, une grande partie de la cryptographie actuelle serait cassée. Dans l'autre cas, on saurait que pour des milliers de problèmes, aucune astuce ne donnera d'algorithme rapide.
Par où commencer
- La théorie de la complexité, une branche de l'informatique théorique et des mathématiques.
- Un premier pas : comprendre pourquoi vérifier une grille de sudoku est facile alors que résoudre ce type de problème en général ne l'est pas.
- Lire la description officielle du problème sur le site de l'institut Clay, ci-dessous.
Pour aller plus loin
Le problème P ≟ NP est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire, et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP ou de démontrer que ce n'est pas démontrable.
Extrait de l'article Wikipédia « Problème P ≟ NP » (licence CC BY-SA).