Главная
Study mode:
on
1
Introduction
2
Polynomial Time Hierarchy
3
Quantifying over circuits
4
Defining complexity classes
5
Examples
6
Complexity Classes
7
There exists for all P
8
min circuit problem
9
min popular hypothesis
10
min unsurprising observation
11
min alternation
Description:
Explore the Polynomial Time Hierarchy in this graduate-level lecture on Computational Complexity Theory. Delve into advanced topics including quantifying over circuits, defining complexity classes, and examining examples. Learn about the "There exists for all P" concept, the min circuit problem, popular hypotheses, and unsurprising observations related to the hierarchy. Gain insights into alternation and its role in complexity theory. Part of Carnegie Mellon's Course 15-855 (Fall 2017), this lecture is taught by Ryan O'Donnell and includes suggested readings from Arora--Barak Chapters 5.1--5.3.

The Polynomial Time Hierarchy: Graduate Complexity Lecture at CMU

Ryan O'Donnell
Add to list
0:00 / 0:00