7 Subset Sum (English)

Valeur des informations & solidité de l’argumentation

La valeur pédagogique est élevée : la vidéo détaille les réductions de manière progressive, en s’appuyant sur des exemples numériques concrets qui facilitent la compréhension. L’argumentation est solide, car elle suit les preuves classiques de NP-complétude (encodage, vérification en temps polynomial, et réduction polynomiale). Chaque construction est justifiée par des invariants clairs (ex. colonnes sans retenue, sommes ciblées). Toutefois, la démonstration est parfois rapide, et certains passages reposent sur des transparents non visualisés dans la transcription, ce qui peut rendre la vérification malaisée. Globalement, le raisonnement est rigoureux et fidèle aux techniques standard de théorie de la complexité.

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

La rigueur scientifique est correcte : les réductions présentées sont des classiques bien établis (CLRS, Garey & Johnson), même si aucune source formelle n’est citée explicitement dans la vidéo. La qualité des sources est indirecte, l’auteur s’appuyant sur des résultats connus. L’adéquation titre/contenu est partielle : le titre annonce ‘Subset Sum’, mais la deuxième moitié porte sur la coloration de graphes, ce qui peut surprendre. Aucun commentaire n’étant fourni, l’analyse des tendances du public n’est pas possible.

Le titre mentionne principalement 'Subset Sum', mais la vidéo couvre aussi d'autres problèmes NP-complets (coloration de graphes). L'adéquation est partielle, le contenu dépassant largement le seul problème annoncé.

8/10

Le contenu expose correctement les réductions standard entre problèmes NP-complets, avec des exemples chiffrés. La transcription comporte des erreurs de reconnaissance vocale (ex. 'nitrogen monophosphide' pour 'NP-complete'), mais la logique mathématique reste juste et cohérente.

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

• 00:02Introduction au problème de la somme de sous-ensemble et objectifs de la vidéo.
• 00:41Rappel de la hiérarchie des réductions NP-complètes (Circuit-SAT, 3-SAT, etc.).
• 01:29Définition formelle du problème de la somme de sous-ensemble et exemple.
• 02:16Début de la preuve de NP-complétude : vérification en temps polynomial et réduction de 3-SAT.
• 03:15Construction de l'encodage numérique d'une instance 3-SAT en instance subset sum.
• 04:17Exemple concret de formule 3-CNF et de sa transformation en nombres.
• 09:20Retour sur la réduction classique de 3-SAT à subset sum avec explication détaillée du tableau.
• 11:17Conversion complète en instance subset sum : choix des littéraux et valeurs de clause.
• 15:57Introduction au problème de coloration de graphes et exemples (pentagone, Sudoku).
• 16:463-coloration : difficulté NP et schéma de réduction depuis 3-SAT.
• 17:474-coloration : réduction simple depuis 3-coloration par ajout d'un sommet universel.
• 19:56Conclusion et mention d'un compendium en ligne des problèmes NP-durs.

• Compendium de dureté NP (mentionné en fin de vidéo) — Ressource en ligne recommandée par l'orateur pour trouver des exemples de réductions.