Undergrad Complexity at CMU - Hardness within P

Explore the intricacies of computational complexity theory in this undergraduate lecture from Carnegie Mellon University's Course 15-455. Delve into the concept of hardness within P, focusing on topics such as the Time Hierarchy Theorem, Strong Exponential Time Hypothesis, and fine-grained complexity. Learn about important problems like all-pairs shortest paths, k-clique, and context-free grammar parsing. Examine reduction techniques, including contrapositive and reduction algorithms, and discover new hardness results. Note a correction regarding the reduction from CNF-SAT to DIAMETER, where the truth assignment vertices need specific connections to special nodes. Engage with open questions in the field and gain insights from Professor Ryan O'Donnell's expertise in this comprehensive 82-minute session from Spring 2017.