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

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.