What Makes P vs. NP So Hard? (P ≠ EXPTIME, Time Hierarchy, Baker-Gill-Solovay)

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

—

References:

Lectures:

[UndefinedBehavior]

A few notes:

1) Trying to pronounce "executor" when you got Pokémon on the mind is very difficult.
2) We now have outro music thanks to Gravity Sound! His channel is linked in the description box.

[Y_M_Alhamdan]

Thanks for the video, just one note: At 1:07 Note that for example 2^{n^4} doesn't belong to O(2^n) but does belong to EXPTIME.

[october]

Been looking forward to a new video form you for a while! I know it will be great.

[EgggPie]

I don't understand how you guys don't have more subscribers. I hope that you guys will get a nice influx of subs soon. Great video!

[reinerczerwinski]

According to Baker-Gill-Solovay P vs. NP cannot be solved with diagonalization alone. But there are several oracles, where P vs. NP is solved relative to them, i.e.for oracle A : P^A (un)equal NP^A is known. Thus, why everyone thinks, the problem P^X vs. NP^X is hard, when X is the empty set?

[Mu_Lambda_Theta]

From the Baker-Gill-Solovay-Theorem, I get the following impression.


If P = NP, the best way to prove it would be to actually build an algorithm to solve NP problems.
If P =/= NP, the best way to prove it would be to prove that everything that is provable is provable with diagonalization.
Or P vs NP is unsolvable. Logic trolling us like that could also be the case.
Or even worse: Proving proving P vs NP is impossible is impossible. Headache.

[raggedclawstarcraft]

Love your channel. Please continue working on it.

[dannyundos]

Every time you say "Gödel", YouTube's automatic caption generator recognizes it as "girdle".

[soulintent]

This channel is phenomenal, i love it

[TusharSachdev]

Most under-rated Math channel on youtube!

[sonali.]

Sir please tell me from which app you made this vedio.??🙏🙏🙏🙏🙏🙏

[jhoaopereyra]

My parents are getting divorced :( What should I do?






Undefined Behavior:
Diagonalization!

[onurcanisler]

*My brain just stopped working... I have forgotten all the topics I have learned in your previous videos... I mean I have forgotten what I was studying*

[irmaksaglam]

<3<3<3 Greeeaaat content, thank you very much.

[jonsaft]

I was a bit unsatisfied by the baker-gill-solovay explanation, too handwavy :(

[MrMentalpuppy]

Assuming an infinitely powerful super computer, what would happen?

[want-diversecontent]

Proving that exptime is equal to NP disproves P=NP.

[SKyrim]

I don't understand why you can say that P is surely listable. Your argument seems to rely on this...

[rit]

I wonder why u have so less likes,
I mean don't people value informative+ creative content.

[BryanLeeWilliams]

Was there an explanation of NP? If there was I missed it.