Undergrad Complexity at CMU - Lecture 21: Randomized Complexity: RP, coRP, and ZPP

Item: Undergrad Complexity at CMU - Lecture 21: Randomized Complexity: RP, coRP, and ZPP
Rating: 5
Author: PostSingularity Institute

par Ryan O'Donnell

Sciences formelles & physiques Informatique & Cybersécurité UYInformatique UYAInformatique théorique

🎙 Ryan O'Donnell 👥 14K 📅 3 juillet 2017 ⏱ 81 min 👁 3K 📄 cours magistral 🧭 2026-08-17

Disponible en : Français (actuel) English

Mots-clés

randomisationcomplexitéRPcoRPZPP

Résumé

Ce cours de la série ‘Undergraduate Complexity Theory’ de l’université Carnegie Mellon, donné par Ryan O’Donnell, introduit les classes de complexité randomisées RP, coRP et ZPP. Le professeur commence par motiver l’utilisation de l’aléatoire en algorithmique, en présentant des exemples classiques où les algorithmes randomisés surpassent les algorithmes déterministes connus : test de primalité (Miller-Rabin), recherche de médiane, vérification de produit de matrices (Freivalds), arbre couvrant minimal, 3-SAT, problème ST-connectivité, couplage parfait dans les graphes bipartis, et test d’identité polynomiale. Il discute ensuite des raisons pour lesquelles l’aléatoire est utile (nécessité pour certaines applications comme la simulation ou la cryptographie) et des réserves (erreur, génération de bits aléatoires). Il définit formellement une machine de Turing probabiliste comme une machine de Turing non déterministe avec deux fonctions de transition, choisies aléatoirement à chaque étape. Il introduit ensuite les classes RP (erreur unilatérale, acceptation avec probabilité > 0 si le mot est dans le langage, rejet certain sinon), coRP (erreur unilatérale de l’autre côté) et ZPP (erreur bilatérale, mais avec temps attendu polynomial). Il explique les relations entre ces classes et avec P et NP, et mentionne la possibilité d’amplification de la probabilité de succès par répétition. Le cours se termine par une discussion sur la question ouverte de la dérandomisation, c’est-à-dire la possibilité de simuler tout algorithme randomisé polynomial par un algorithme déterministe polynomial (question P vs BPP).

227 mots

Évaluation critique

Valeur des informations & solidité de l’argumentation

La valeur des informations est très élevée : le cours fournit une introduction rigoureuse et complète aux classes de complexité randomisées, avec des définitions formelles, des exemples concrets et des discussions sur les relations entre classes. L’argumentation est solide : chaque concept est motivé, illustré par des exemples historiques et des résultats connus, et les preuves sont esquissées ou renvoyées à des lectures. Le professeur adopte une démarche pédagogique progressive, partant des intuitions pour arriver aux définitions formelles. La discussion sur la dérandomisation est nuancée et ouvre des perspectives de recherche.

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

La rigueur scientifique est exemplaire : le cours est dispensé par un professeur de l’université Carnegie Mellon, spécialiste de la théorie de la complexité. Les définitions sont précises et conformes à la littérature. Les sources mentionnées (Sipser, chapitre 10.2) sont pertinentes pour approfondir. Le titre est parfaitement adéquat : il annonce exactement le contenu de la leçon. Aucune source externe n’est citée dans la vidéo, mais les liens de la description renvoient vers le site du cours et la page du professeur, ce qui renforce la crédibilité.

193 mots

Adéquation titre / contenu

Le titre correspond exactement au contenu : la leçon traite des classes de complexité randomisées RP, coRP et ZPP.

Qualité & fiabilité

9/10

Cours universitaire de niveau undergraduate par un professeur de Carnegie Mellon, contenu rigoureux et précis, conforme aux définitions standards de la théorie de la complexité.

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

Site du cours 15-455 — Page officielle du cours de complexité computationnelle de Carnegie Mellon.
Page personnelle de Ryan O'Donnell — Page du professeur, permettant de vérifier ses travaux et son enseignement.
Panopto — Logiciel de capture de cours utilisé pour filmer la vidéo.

Sources concordantes

Sipser, Introduction to the Theory of Computation — Ouvrage de référence mentionné dans la description comme lecture suggérée.

Apport & nouveautés

Ce cours apporte une introduction claire et structurée aux classes de complexité randomisées, avec une présentation pédagogique des définitions et des exemples. Il met en lumière l’importance de la randomisation en algorithmique et les questions ouvertes qui en découlent.

Pour aller plus loin :

Complexité algorithmique — Article de synthèse sur les classes de complexité.
Machine de Turing probabiliste — Définition et propriétés.
Test de primalité — Présentation des algorithmes de primalité, dont Miller-Rabin.
Problème P = NP — Contexte des classes de complexité.

84 mots

Profil radar

Le profil radar montre un contenu très équilibré, avec des scores élevés dans toutes les dimensions : quantité d'information, qualité, niveau technique et fiabilité. Cela reflète un cours universitaire rigoureux et dense, adapté à un public étudiant avancé.

Fiabilité 9/10