4 P, NP, NP completeness (English)

Valeur des informations & solidité de l’argumentation

La valeur pédagogique est remarquable : chaque nouveau concept est introduit par une analogie, illustré par des graphes commentés, puis formalisé avec précision. L’argumentation suit une progression logique qui relie les problèmes concrets (TSP, Euler, Hamiltonian) aux définitions abstraites des classes de complexité. Les réductions sont expliquées étape par étape, ce qui permet de comprendre pourquoi un problème est au moins aussi dur qu’un autre. La démonstration de l’appartenance à NP (vérification d’un certificat) est systématiquement présentée pour chaque exemple. L’utilisation d’une machine de Turing non déterministe pour expliquer NP est claire et correcte. La trame argumentative est solide et sans faille, avec notamment la distinction entre problèmes de décision et d’optimisation, et le rôle clé des réductions dans la preuve de dureté.

Rigueur scientifique, qualité des sources, adéquation du titre

La rigueur scientifique est irréprochable : les définitions données correspondent aux standards de la littérature (notamment la caractérisation par machines de Turing et le rôle des certificats). Le titre est parfaitement adéquat : il reflète exactement le sujet couvert. En ce qui concerne les sources, le cours mentionne les travaux fondamentaux de Cook (1971) et Karp (1972), mais aucune référence précise n’est donnée sous forme de lien ou de citation complète ; la description de la vidéo est vide. Cela limite la possibilité de vérification externe, mais n’affecte pas la justesse du contenu, qui s’appuie sur des notions solidement établies.

Le titre décrit exactement le contenu : la classification des problèmes P, NP et NP-complets. La mention 'English' indique la langue du cours.

9/10

Exposé clair et rigoureux des concepts fondamentaux de la théorie de la complexité, conforme aux définitions standards. Les explications sont précises et structurées, bien que la vidéo ne cite pas directement de sources primaires (les références historiques à Cook et Karp sont mentionnées).

Repères établis par PSI à partir de la transcription : le créateur n'a pas défini de chapitres.

• 00:00Introduction aux classes P, NP et NP-complets avec analogies.
• 04:30Présentation du problème du voyageur de commerce (TSP).
• 10:00Explication des tours eulériens et des cycles hamiltoniens.
• 15:50Le problème SAT : définition et vérification en NP.
• 21:40Différence entre 2SAT et 3SAT et impact sur la complexité.
• 26:40Problèmes de décision vs problèmes d'optimisation, réduction entre les deux.
• 33:20Définition formelle de P et NP, machines de Turing et certificats.
• 40:00Réductions polynomiales : principe et exemple avec le plus court chemin.
• 46:40NP-dur et NP-complet : conditions, dureté préservée par réduction.
• 51:40Historique : Cook (1971) et Karp (1972), carte des réductions et conclusion.

• The Complexity of Theorem-Proving Procedures — Article fondateur de Stephen Cook (1971) où il démontre que le problème de satisfiabilité des circuits est NP-complet, introduisant la notion de NP-complétude.
• Reducibility Among Combinatorial Problems — Article de Richard Karp (1972) qui établit 21 problèmes NP-complets via des réductions polynomiales, donnant naissance au domaine de la complexité computationnelle.