Undergrad Complexity at CMU - Lecture 13: Search-to-Decision, Padding, Dichotomy Theorems

Valeur des informations & solidité de l’argumentation

La valeur des informations est élevée : le cours présente des résultats fondamentaux de la théorie de la complexité avec des preuves complètes et des exemples concrets. L’argumentation est solide, chaque théorème étant démontré rigoureusement, avec des explications intuitives. La réduction de la recherche vers la décision est illustrée par des exemples comme SAT et la 3-coloration, et la preuve générale est donnée. Le padding est expliqué clairement avec des exemples de réductions. Les théorèmes de dichotomie sont présentés avec leur portée et leurs limites. L’ensemble est cohérent et pédagogique.

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

La rigueur scientifique est excellente : le contenu est conforme aux connaissances établies en complexité computationnelle, et les preuves sont correctes. Les sources sont implicites (cours de référence, travaux de Cook, Levin, Ladner), mais le professeur est une autorité reconnue. Le titre est en adéquation parfaite avec le contenu. Aucun commentaire n’est fourni, donc aucune analyse des tendances du public n’est possible.

Le titre décrit précisément le contenu : la leçon 13 du cours de complexité computationnelle de premier cycle à CMU, couvrant les sujets annoncés.

9/10

Cours universitaire de niveau undergraduate par un professeur reconnu en complexité computationnelle, avec un contenu rigoureux et des démonstrations détaillées. La qualité est élevée, mais il s'agit d'un cours magistral, pas d'une publication originale.

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

• 00:00Introduction et rappel du cours, questions ouvertes sur la complexité.
• 05:00Début de la section sur la réduction de la recherche vers la décision, exemple de SAT.
• 10:00Algorithme pour trouver une assignation satisfaisante en utilisant l'oracle de décision.
• 15:00Extension à la 3-coloration et discussion sur les instances partielles.
• 20:00Preuve générale pour tout problème NP en utilisant le théorème de Cook-Levin.
• 25:00Introduction au padding et à son utilisation pour comparer les classes de complexité.
• 30:00Exemples de padding et implications pour P vs NP.
• 35:00Théorème de Ladner et existence de problèmes NP-intermédiaires.
• 40:00Discussion sur les théorèmes de dichotomie et leur portée.
• 45:00Conclusion et perspectives pour la suite du cours.

• Site du cours 15-455 — Page officielle du cours, contient les notes et références.
• Page personnelle de Ryan O'Donnell — Page du professeur, avec ses publications et cours.
• Panopto — Plateforme de capture vidéo utilisée pour enregistrer le cours.

• Computational Complexity: A Modern Approach — Ouvrage de référence en complexité, couvre les mêmes sujets.
• The Complexity of Theorem-Proving Procedures — Article de Cook (1971) introduisant la NP-complétude.