Algebraic "NP vs. P" vs. "Boolean NP vs. P": Graduate Complexity Lecture 15 postscript at CMU

Algebraic "NP vs. P" vs. "Boolean NP vs. P": Graduate Complexity Lecture 15 postscript at CMU

par Ryan O'Donnell

Sciences formelles & physiques Informatique & Cybersécurité UYInformatiqueUYAInformatique théorique
🎙 Ryan O'Donnell 👥 14K 📅 7 novembre 2017 ⏱ 14 min 👁 639 📄 cours magistral 🧭 2026-08-17
Disponible en : Français (actuel) English

Mots-clés

complexité algébriqueNP vs PP/polypermanentthéorie de la complexité

Résumé

Cette vidéo est un complément à la leçon 15 du cours de complexité computationnelle de deuxième cycle à Carnegie Mellon. Ryan O’Donnell corrige un théorème énoncé précédemment : il précise que l’hypothèse correcte pour obtenir la séparation entre les classes algébriques AlgNP/poly et AlgP/poly est NP ⊄ P/poly, et non simplement NP ≠ P. Il explique la preuve par contraposée : si AlgNP/poly = AlgP/poly, alors le permanent est calculable par des circuits algébriques de taille polynomiale, et on peut le convertir en circuit booléen polynomial, ce qui implique NP ⊆ P/poly. Il discute des difficultés techniques liées aux constantes utilisées dans les circuits algébriques, notamment leur taille et leur nature (rationnelles ou complexes). Il mentionne que, sous l’hypothèse simplificatrice de constantes rationnelles à bits polynomialement bornés, la conversion est directe en travaillant modulo un grand nombre premier. Pour le cas général, il invoque des résultats de Bürgisser et Koiran sur l’élimination des constantes, qui nécessitent l’hypothèse de Riemann généralisée (GRH) pour les corps infinis. La vidéo se conclut en rappelant le théorème corrigé et son implication pour la hiérarchie polynomiale.

181 mots

Évaluation critique

Valeur des informations & solidité de l’argumentation

La vidéo apporte une valeur certaine pour un public averti en complexité computationnelle. Elle corrige une imprécision d’un cours précédent, ce qui démontre une rigueur intellectuelle. L’argumentation est solide : la preuve est présentée par contraposée, avec une esquisse claire des étapes clés. L’exposé met en évidence les subtilités techniques (constantes, corps de base, GRH) et les résultats auxiliaires utilisés. La démarche est pédagogique et précise, bien que très technique.

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

La rigueur scientifique est élevée : le contenu est un cours universitaire de niveau avancé, dispensé par un chercheur reconnu en complexité. Les sources sont implicites mais identifiables : les travaux de Bürgisser et Koiran sont mentionnés, et le cours s’appuie sur des références standards. Le titre est parfaitement adéquat au contenu, décrivant précisément le sujet traité. Aucune source externe n’est citée dans la description, mais les liens vers la page du cours et la page personnelle de l’enseignant sont fournis.

166 mots

Adéquation titre / contenu

Le titre reflète exactement le contenu : une comparaison entre les versions algébrique et booléenne de la question NP vs P.

Qualité & fiabilité

8/10

Exposé rigoureux d'un théorème de complexité algébrique, avec correction d'une erreur énoncée précédemment, preuve esquissée et mention des hypothèses techniques (GRH). Le contenu est spécialisé et s'appuie sur des résultats publiés (Bürgisser, Koiran).

Moments clés

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

Sources citées

Sources concordantes

Apport & nouveautés

Cette vidéo apporte un éclairage précis sur la relation entre les classes de complexité algébriques et booléennes, en corrigeant une erreur d’énoncé et en détaillant la preuve d’un théorème important. Elle met en évidence les subtilités techniques liées aux constantes et au corps de base, et montre comment des résultats de théorie des nombres (GRH) interviennent en complexité algébrique.

Pour aller plus loin :

  • Complexité algébrique — Article Wikipédia sur la complexité algébrique, utile pour le contexte.
  • P/poly — Article Wikipédia sur la classe P/poly, pertinente pour comprendre les circuits non uniformes.
  • Théorème de Karp-Lipton — Article Wikipédia sur le théorème de Karp-Lipton, mentionné dans la vidéo.
  • Hypothèse de Riemann généralisée — Article Wikipédia sur la GRH, utilisée dans la preuve.
  • Permanent (mathématiques) — Article Wikipédia sur le permanent, objet central de la vidéo.

134 mots

Profil radar

Le profil radar montre une très haute qualité d'information et un niveau technique élevé, avec une quantité d'information modérée. La fiabilité globale est bonne, mais la quantité d'information est limitée par la durée courte de la vidéo.

Fiabilité 8/10