Hierarchy Theorems - Time, Space, and Nondeterministic: Graduate Complexity Lecture at CMU

Explore the intricacies of hierarchy theorems in computational complexity theory in this graduate-level lecture from Carnegie Mellon University. Delve into time, space, and nondeterministic hierarchies as part of the Fall 2017 Computational Complexity Theory course. Learn about encoding schemes, Turing machines, time constructibility, and nondeterministic certificates. Examine the Time Hierarchy Theorem in depth, including potential bugs in its proof and the concept of crazy functions. Gain insights into nondeterministic complexity through discussions on guessing bits and certificates. Supplement your learning with suggested readings from Arora-Barak Chapters 3.1, 3.2, and optionally 1.7 for those interested in O(T log T) simulation.

Introduction
Time Hierarchy Theorem
Encoding Scheme
Multiple Encodings
Turing Machine
DS Action
Bug in the Proof
Recall
Crazy Functions
Time Constructible
Nondeterministic
Nondeterministic Certificates
Guessing Bits