Understanding Why P vs. NP Is So Challenging

There are a lot of unsolved problems in complexity theory, but there are a few things we do know. We look at the Time Hierarchy Theorem, and also why the proof techniques don't transfer to P vs NP.

Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Justin Chen, Zachary Greenberg, Elaine Chang, Brandon Chen
Music: Gravity Sound (https://www.youtube.com/channel/UCQ7Xmyu6eXpJfkEoMtRMv1w)

Twitter: https://twitter.com/UBehavior

—

References:
P vs NP Playlist: https://www.youtube.com/playlist?list=PLlwsleWT767dnN25K_QgvdKkovK_t4K6-
Exptime: https://en.wikipedia.org/wiki/EXPTIME
Time Hierarchy Theorem: https://en.wikipedia.org/wiki/Time_hierarchy_theorem
Baker-Gill-Solovay: https://www.quora.com/What-is-an-intuitive-explanation-of-the-natural-proof-relativization-and-algebrization-barriers-to-solving-the-P-vs-NP-problem
Oracles: https://en.wikipedia.org/wiki/Oracle_machine#Complexity_classes_of_oracle_machines
Relativization: https://ocw.mit.edu/courses/mathematics/18-405j-advanced-complexity-theory-spring-2016/lecture-notes/MIT18_405JS16_Relativ.pdf
The Role of Relativization in Complexity Theory: http://people.cs.uchicago.edu/~fortnow/papers/relative.pdf

Lectures:
Time Hierarchy Theorem: https://youtu.be/J92OKdVxjYM
Why is P vs. NP Difficult?: https://youtu.be/l74BCSajWjo