Unraveling the Biggest Mystery in Computer Science: P vs NP 🧩

This is my entry to #SoME4, Grant Sanderson’s Summer of Math Exposition Competition!

The P vs NP problem is widely agreed upon as the biggest unsolved question in computer science, asking whether discovery is harder than recognition -- if the solution to a problem is easily verifiable (like in sudoku, for example), does it also mean there’s an efficient way to find solutions in the first place? Our intuition says this should not be the case -- that solving a sudoku puzzle should be a lot harder than checking the solution once everything’s filled in.
In 1956, despite the fact that computer science was a new discipline and hadn’t developed the theory and terminology we’d use today, Kurt Gödel was already pondering what the ultimate limits of computation might be, and he essentially foretold the P vs NP question 15 years before Stephen Cook would formalize it in 1971.
In this video, we explore the P vs NP problem through that historical lens, thinking about the problem originally as Gödel did, in terms of a computer program trying to automatically find mathematical proofs, and eventually building up to the actual definitions of P and NP through a series of examples such as graph coloring.

This video is dedicated in loving memory of my uncle, Leonard Gojer, who was enthralled by the P vs NP problem and the biggest mysteries of our universe.

Support me on Patreon! https://www.patreon.com/PurpleMindCreations
If you'd like to aid the success of this channel, this is the best way to do it! Every contribution is sincerely, greatly, appreciated.

If you or your institution is interested in sponsoring the topic of a future PurpleMind video, please contact me via purplemindcs@gmail.com!

Erratum:
4:29 10000^2 = 100 million, not 10 million. Whoops! However the point still stands -- 100 million computational steps is still comfortably within reach for modern computers.

References:
Godel’s letter (full text): https://www.anilada.com/notes/godel-letter.pdf
3-Colorability paper: https://arxiv.org/pdf/cs/0006046
Millennium Prize Problems: https://en.wikipedia.org/wiki/Millennium_Prize_Problems

Brittle Rille - Reunited by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/by/4.0/

Math animations are made using Manim, by 3Blue1Brown.
Character animation done by Osama Mohamed.

Discord Server: https://discord.gg/smuxnzZ5Zf. Feel free to join!
Business Inquiries: purplemindcs@gmail.com