Undergrad Complexity at CMU - Problems in P

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.

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