What is the Time Hierarchy Theorem? - Easy Theory

Here we prove the time hierarchy theorem, which says that for any "sufficiently suitable" function t(n), there is a language solvable in O(t(n)) time and not in o(t(n) / log t(n)) time.

#easytheory

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Social Media:

Merch:

▶SEND ME THEORY QUESTIONS◀

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

[EasyTheory]

Thanks to Micah Wood (Platinum), and Josh Hibschman, Timmy Gy, Patrik Keinonen, and Travis Schnider (Silver) for helping support this video. If you want to contribute, links are in the video description.

[planetariansaturn]

Hi, I am struggling with the complexity theory in my class and thanks to you there is no language barrier no more, thanks a lot for all your videos!

[aleksandrakulbaka]

Thank you so much for this video, I finally understood why THT holds!
It's the easiest to follow proof I have seen :)

[YazBelinskiy]

This is awesome! Using Sipser notation is even more awesome!