Toda's 1st Theorem and the Permanent: Graduate Complexity Lecture 14 at CMU

Toda's 1st Theorem and the Permanent: Graduate Complexity Lecture 14 at CMU

par Ryan O'Donnell

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

Mots-clés

Toda's theorempermanentparity Pcomplexity classesValiant-Vazirani

Résumé

Ce cours de complexité computationnelle de niveau graduate, donné par Ryan O’Donnell à Carnegie Mellon, se concentre sur deux sujets principaux. La première partie est consacrée à la preuve du premier théorème de Toda, qui établit que la hiérarchie polynomiale (PH) est contenue dans BPP^⊕P (ou plus précisément dans P^#P). La preuve s’appuie sur trois ingrédients : le théorème de Valiant-Vazirani, la fermeture de ⊕P sous lui-même (⊕P^⊕P = ⊕P), et la relativisation du théorème NP ⊆ BPP ⇒ PH ⊆ BPP. Le professeur détaille la preuve en explicitant la construction de circuits avec portes Oracle et en montrant comment le théorème de Valiant-Vazirani se relativise. La seconde partie introduit le problème du permanent, une fonction qui compte les permutations pondérées d’une matrice, et souligne sa complétude pour la classe #P. Le permanent est comparé au déterminant : alors que le déterminant est calculable en temps polynomial, le permanent est #P-complet, ce qui en fait un problème très difficile. Le cours mentionne également des propriétés remarquables du permanent, comme la réductibilité aléatoire et l’existence d’un vérificateur d’instances, qui seront étudiées plus tard.

182 mots

Évaluation critique

Valeur des informations & solidité de l’argumentation

La valeur des informations est très élevée : le cours fournit une preuve complète et détaillée du premier théorème de Toda, un résultat central en complexité computationnelle. L’argumentation est rigoureuse, avec une attention particulière portée à la relativisation et aux subtilités des classes avec Oracle. Le professeur prend soin de détailler les étapes clés, comme la construction de circuits avec portes Oracle et l’application du théorème de Valiant-Vazirani. La présentation du permanent est également solide, avec une comparaison éclairante avec le déterminant et une mise en perspective de sa complétude pour #P. Les explications sont claires et adaptées à un public de niveau graduate, avec des rappels des résultats précédents.

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

La rigueur scientifique est excellente : le cours est dispensé par un expert reconnu, et les preuves sont présentées avec soin. Les sources mentionnées incluent le manuel de référence Arora-Barak (chapitres 17.4, 8.6.2, 17.3.1) et le site du cours. Le titre est parfaitement adéquat au contenu, qui traite effectivement du premier théorème de Toda et du permanent. La qualité des sources est élevée, bien que la vidéo soit une prise de cours sans édition, ce qui peut inclure des hésitations ou des digressions.

208 mots

Adéquation titre / contenu

Le titre décrit exactement le contenu : la première partie est consacrée au premier théorème de Toda, la seconde au permanent comme problème complet pour #P.

Qualité & fiabilité

8/10

Cours magistral de niveau graduate par un professeur reconnu en complexité computationnelle, avec preuves détaillées et références à des ouvrages standards. La rigueur est élevée, mais la vidéo est une prise de cours, sans édition ni vérification factuelle supplémentaire.

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

Ce cours apporte une preuve détaillée et pédagogique du premier théorème de Toda, un résultat fondamental qui relie la hiérarchie polynomiale à la classe #P. L’originalité réside dans l’explication minutieuse de la relativisation et de la manipulation des classes avec Oracle, souvent source de confusion. De plus, l’introduction du permanent comme problème complet pour #P est claire et met en évidence ses propriétés remarquables, comme la réductibilité aléatoire et le vérificateur d’instances, qui seront approfondies dans la suite du cours.

Pour aller plus loin :

  • Théorème de Toda — Article Wikipédia détaillant le théorème et ses implications.
  • Permanent (mathématiques) — Définition et propriétés du permanent.
  • Classe #P — Article sur la classe de complexité #P et sa complétude.

118 mots

Profil radar

Le profil radar montre des scores très élevés en quantité et qualité d'information, ainsi qu'un niveau technique maximal, reflétant un cours avancé et dense. La fiabilité globale est légèrement inférieure en raison du format non édité, mais reste solide.

Fiabilité 8/10