ETH False

Valeur des informations & solidité de l’argumentation

Valeur des informations : le cours fournit une vue détaillée d’une tentative de preuve au cœur de la complexité : réduction au permanent, calcul DP, matrice polynomiale, interpolation. Il est précieux pour comprendre comment un expert aborde une preuve non rodée, avec ses doutes et ses allers-retours. L’originalité tient à la mise en œuvre d’outils classiques (Valiant, Ryser, interpolation) pour un résultat potentiellement majeur. Solidité de l’argumentation : l’enseignant expose les étapes dans un ordre logique et justifie chaque réduction ; il prend soin de distinguer ce qui est acquis de ce qui reste à vérifier. Cependant, la démonstration n’est pas complète : plusieurs passages sont admis ou renvoyés à la preuve d’OpenAI, et l’on sent que la présentation est improvisée. L’argumentation est donc solide sur les maillons explicitement détaillés, mais ne peut pas être considérée comme une preuve autonome.

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

Rigueur scientifique : la méthode est celle d’un séminaire exploratoire ; l’auteur rappelle des théorèmes classiques (Valiant, Ryser) et fait preuve de transparence sur les limites de sa compréhension. Le recours à un assistant IA pour compléter la preuve est annoncé, ce qui est honnête mais introduit une source d’erreur supplémentaire. La qualité des sources est inégale : les outils classiques sont bien identifiés, mais la preuve récente d’OpenAI n’est ni nommée précisément ni reliée à un document public dans la description. Adéquation titre/contenu : le titre « ETH False » est plus affirmatif que le contenu, qui parle de « tentative » ; il convient néanmoins au thème principal.

Le titre est plus affirmatif que le contenu, qui parle d'une tentative de preuve ; il reste thématiquement adapté.

6/10

Démarche experte mais improvisée, preuve récente non publiée et non vérifiée, nombreux détails assumés comme non maîtrisés par l'auteur.

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

• 01:00Introduction : tentative de prouver que ETH est fausse ; objectif : 3-SAT en temps sous-exponentiel.
• 08:00Réduction de Sharp-3-SAT au calcul du permanent ; rappel de la définition du permanent.
• 15:00Algorithme de programmation dynamique en O(2^n) pour le permanent (mémorisation, formule de Ryser).
• 25:00Plan principal : construire une matrice polynomiale A(T) de faible degré, calculer les permanents de A_i et utiliser l'interpolation.
• 45:00Calcul des dérivées de perm(A(T)) et interpolation à partir des valeurs en L points.
• 1:05:00Discussion sur la portée de la réduction, la sparsification et les questions des étudiants.

• Preuve OpenAI de la fausseté de l'ETH (mentionnée en vidéo) — Point de départ de la tentative ; annoncée comme parue quelques jours avant le cours.
• Réduction de Valiant de #3-SAT au permanent (rappels du cours) — Utilisée pour ramener le comptage SAT au calcul du permanent.
• Formule de Ryser pour le permanent — Mentionnée comme algorithme en O(n 2^n) pour le calcul du permanent.