Explore undergraduate computational complexity theory in this 1-hour 22-minute lecture from Carnegie Mellon's Course 15-455. Delve into simulations and Turing machine variants, covering topics such as the Time Hierarchy Theorem, new complexity classes, and the definition of P. Examine natural problems and the goals of computer science, including brute-force algorithms and problems within P. Learn about running time, paths, breadth-first search, and coloring algorithms. Investigate the longest common subsequence problem, brute force solutions, and recursion. Enhance your understanding of fundamental concepts in computational complexity with suggested readings from Sipser Ch. 7.2 on PATH and RELPRIME.
Overview
Syllabus
Time Hierarchy Theorem
New Complexity Class
What is P
Natural problems
Goal of computer science
Bruteforce algorithms
Problems in P
Running time
Paths
Breadthfirst search
Two coloring
Two coloring algorithm
Three coloring algorithm
Longest common subsequence
Brute force solution
Recursion
Taught by
Ryan O'Donnell
Related Courses
-
Data Structures & Algorithms IV: Pattern Matching, Dijkstra’s, MST, and Dynamic Programming Algorithms
5.0 -
Undergrad Complexity at CMU - NP
-
Undergrad Complexity at CMU - Savitch's Theorem and NL
-
Undergrad Complexity at CMU - Hardness within P
-
The Polynomial Time Hierarchy: Graduate Complexity Lecture at CMU
-
Circuits - Graduate Complexity Lecture 4 at CMU
