The Polynomial Time Hierarchy: Graduate Complexity Lecture 7 at CMU

The Polynomial Time Hierarchy: Graduate Complexity Lecture 7 at CMU

by Ryan O'Donnell

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Ryan O'Donnell 👥 14K 📅 September 29, 2017 ⏱ 79 min 👁 3K 📄 lecture 🧭 2026-08-17
Available in: English (current) Français

Keywords

polynomial hierarchycomplexity classesNPcoNPalternation

Summary

This is a graduate-level lecture on the polynomial time hierarchy (PH), taught by Ryan O’Donnell at Carnegie Mellon University. The lecture begins by motivating PH through the question: if P=NP, what else becomes polynomial-time solvable? It shows that the minimum circuit problem, which is not known to be in NP or coNP, would become polynomial-time if P=NP. The lecture then formally defines the existential and universal operators on complexity classes, leading to the classes Sigma_i^P and Pi_i^P. It explains how these classes form the polynomial time hierarchy, with P at the bottom and PSPACE as an upper bound. The lecture also discusses the collapse of PH under various assumptions, such as P=NP or NP=coNP, and illustrates how a collapse at any level implies a collapse to that level. The presentation includes examples, intuitive explanations, and references to the textbook by Arora and Barak.

143 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a clear and rigorous introduction to the polynomial time hierarchy, building from basic definitions to important results. The argumentation is solid, with careful explanations of why certain inclusions hold and how collapses occur. The use of the minimum circuit problem as a motivating example effectively illustrates the power of PH. The lecture also offers multiple perspectives, such as quantifier-based definitions and the operator view, which enhances understanding.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with definitions and proofs presented accurately. The instructor references the standard textbook by Arora and Barak, and the course materials are available online. The title accurately reflects the content, and the lecture is well-structured. No external sources are cited beyond the course materials, but the content is consistent with established complexity theory.

142 words

Title / Content Match

The title accurately reflects the content: a graduate lecture on the polynomial time hierarchy.

Quality & Reliability

9/10

Lecture by a renowned professor at CMU, part of a graduate course, with clear definitions, proofs, and references to standard textbook (Arora-Barak).

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

Contribution & Novelties

This lecture provides a clear and thorough introduction to the polynomial time hierarchy, a fundamental topic in computational complexity. It offers intuitive explanations and multiple perspectives, making it accessible to graduate students. The lecture also highlights the significance of PH in understanding the P vs NP problem.

Pour aller plus loin :

83 words

Radar Profile

The radar profile shows high scores across all dimensions, indicating a lecture that is both information-dense and technically rigorous. The balance between quantity and quality of information is excellent, with a strong emphasis on formal definitions and proofs.

Reliability 9/10