Computer Science's Biggest Mystery
Audience: high-schoolundergraduategraduate
Tags: p-vs-np-computational-complexity-graph-coloring-two-colorability-three-colorability-stephen-cook-godel-von-neumann-theoretical-computer-science-polynomial-time-exponential-time-np-computer-science-complexity-theory-millennium-prize
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.
Analytics
Comments
Obviously a very sophisticated production — and a great exposition on P vs NP.
I think this video would be a bit too basic to be appropriate for graduate students, but certainly everyone can enjoy your style and narration.
In terms of novel contributions, I believe the historical lens provided on P vs NP and how it had precursors in the thoughts of Gödel was a nice connection. I think the actual mathematical content was mostly standard for a video on P vs NP, but illustrated very well.
Your explanations were mostly very clear. I never once “lost the thread” of how we got here.
I think what I’ll remember from the video most as my “aha” moment is the difference between 2-coloring (P) and 3-coloring (NP-complete).
Great all around. Great animation, editing, pacing, script, knowledge, tending to both inexperienced and experienced viewers. My one piece of feedback is that, if I have to be a stickler, is that I would be even more engaged if you varied the tone and energy. One of my pet peeves is when the cadence of the video is exactly the same because we as viewers are missing signals about what we should be paying attention to, or whether we should listen, or be ready to be entertained by some action.
Super nice video about a highly covered topic. The reason for my score is that, i think the video lacks that ahh! experience in math. The theorems and examples are either trivial, or too complex to be presented. The 8 language narration is super impressive!!
The visuals really helped make the video not only interesting but also much more clear, especially in showing how graph coloring works. I think it satisfies all the criteria of the guidelines, but I only wish it were longer and talked more about turing machines.
Really fantastic graphics/animation + helpful, well thought out examples throughout. Thanks for sharing!
Yes, this is explained very clearly using 3-colorability of graphs
I really like the explanation of the history because it helps spark interest in the topic
nice historical details
This was a nice video, with fun animations and an inviting style.
However, the market on P vs NP videos is so oversaturated with fantastic videos (such as last year’s SOME winner) that it’s hard to say this sticks out in particular.
A very well made video with quite a good explanation of the basics of P vs NP. The introductory nature does impose some restrictions on pacing which aren’t 100% my preference, particularly toward the beginning, but I’m trying to be impartial regarding that given my bias as someone already quite familiar with the topic - I think the choices you made are more or less right for the video you were making.
Thanks for sharing! I’ll drop a sub, would love to see more from you.
When becoming a mathematician, at least in my case, one of the first things I did was read the millennium prize problems to no avail. This video explains away the vagueness of one of those problems, for which I am grateful. This work reminded me of the videos of Veritasium, yet when Veritasium made a video discussing the same topic, it still failed to make me understand an approachable way to a solution. This video successes, where Veritasium fails.
The visualizations were very engaging and the story-like structure kept me hooked throughout.
This video is pretty good! Following the visual style of Veritasium, the content is also well explained.
Maybe there can be better animations for the reductions, just a bit more detail on how to do them.
And seemingly standing on rail tracks is unnerving for the viewer.
Very long tag lol
Perhaps it could’ve spent more time talking about Reduction and NP-complete problems. That would have brought out possible “Aha” moments.