L'essentiel à connaître
Le problème P vs NP est la question centrale de l'informatique théorique. En termes simples, P regroupe les problèmes qu'un ordinateur peut résoudre rapidement (en temps polynomial, comme le tri d'une liste). NP regroupe les problèmes dont on peut vérifier une solution proposée rapidement. La grande question est de savoir si tout problème dont on peut vérifier la solution rapidement peut aussi être résolu rapidement.
Au sein de NP, il existe une catégorie spéciale : les problèmes NP-complets. Ce sont les problèmes les plus difficiles de NP. Si quelqu'un trouvait un algorithme polynomial pour résoudre un seul problème NP-complet, alors tous les problèmes de NP seraient résolvables en temps polynomial, prouvant ainsi que P = NP. C'est le concept de réduction polynomiale qui permet de lier ces problèmes entre eux.
Définition : P (Polynomial) est la classe des langages décidables par une machine de Turing déterministe en temps polynomial.
À retenir : La plupart des chercheurs pensent que P est différent de NP (P ≠ NP), mais personne n'a encore pu le prouver.
Les points clés
Pour bien comprendre, prends l'exemple du Sudoku. Vérifier si une grille remplie est correcte est très facile (c'est NP). Par contre, remplir une grille vide de taille géante est extrêmement difficile (c'est NP-complet). Parmi les problèmes célèbres, on trouve SAT (satisfiabilité booléenne), le voyageur de commerce (TSP) ou encore le problème du sac à dos. Ils partagent tous cette caractéristique : une explosion combinatoire des possibilités.
Attention à la classe NP-Hard (NP-Difficile). Un problème est NP-Hard s'il est au moins aussi difficile que les problèmes les plus durs de NP, mais il n'a pas besoin d'être lui-même dans NP (on n'a pas forcément besoin de pouvoir vérifier sa solution rapidement). Si un problème est à la fois dans NP et NP-Hard, il est dit NP-complet. Cette nuance est cruciale pour les examens de niveau Master.
Formule : Si A ≤p B et B ∈ P, alors A ∈ P (où ≤p désigne la réduction polynomiale).
Piège classique : Ne confonds pas NP avec "Non-Polynomial". NP signifie "Non-déterministe Polynomial".
Quiz : Teste tes connaissances
Question 1 : Que signifie l'acronyme NP ?
Réponse : B. Cela désigne des problèmes résolvables en temps polynomial sur une machine de Turing non-déterministe. L'erreur commune est de croire que cela signifie "pas polynomial".
Question 2 : Laquelle de ces affirmations est vraie concernant les inclusions de classes ?
Réponse : A. Tout problème que l'on sait résoudre rapidement (P) est par définition vérifiable rapidement (NP). L'inverse n'est pas (encore) prouvé.
Question 3 : Quel a été le premier problème prouvé comme étant NP-complet ?
Réponse : D. C'est le théorème de Cook (1971) qui a démontré que le problème de satisfiabilité des formules booléennes est NP-complet.
Question 4 : Si on prouve qu'un problème NP-complet peut être résolu en O(n^3), qu'est-ce que cela signifie ?
Réponse : C. Comme tout problème de NP peut se réduire polynomialement à un problème NP-complet, trouver un algorithme polynomial pour l'un d'eux rendrait tout NP polynomial.
Question 15 : Un problème NP-Hard est-il nécessairement dans NP ?
Réponse : A. NP-Hard signifie "au moins aussi dur que NP". Il peut exister des problèmes NP-Hard encore plus complexes, comme le problème de l'arrêt, qui n'est même pas décidable.
Comment ORBITECH Peut T'aider
ORBITECH AI Academy met à ta disposition des outils concrets pour réviser plus efficacement et progresser à ton rythme.
- Générateur de Quiz : crée des quiz personnalisés pour tester tes connaissances et identifier tes lacunes.
- Générateur d'Exercices : crée des exercices d'entraînement adaptés à ton niveau avec corrections détaillées.
- Générateur de Résumés : transforme tes cours en fiches de révision claires et structurées.
- Générateur de Mind Maps : visualise et organise tes idées avec des cartes mentales générées automatiquement.
Tous ces outils sont disponibles sur ta plateforme ORBITECH. Connecte-toi et explore ceux qui correspondent le mieux à tes besoins !