THE VIDEO SHELF · computational complexity
P vs. NP and the Computational Complexity Zoo
An 11-minute animated introduction to P vs. NP and the wider landscape of complexity classes, inspired by the Complexity Zoo wiki. It assumes no background in computer science.
Why HN readers recommended it
HN repeatedly recommends it as the best short, funny introduction to P vs. NP and complexity classes for people with no background.
This is a summary from the source dataset, not an endorsement by Hacker News or the video creator.
Video & recommendation details
- Creator / channel
- hackerdashery
- Topic
- computational complexity
- Format
- explainer
- Level
- intro
- HN recommenders in dataset
- 4
- HN mentions in dataset
- 8
- Recommendation years in dataset
- 2015–2026
These counts and years describe the included Hacker News records; they are not YouTube views or the video’s publication date.
From the original HN conversations
Excerpts from the recorded comments. Follow each source for the full comment and surrounding discussion.
There's a fantastic video I refer to every now and then if I'm a bit unsure about it, definitely recommend it - [VIDEO]
sgrove on Hacker News · 2017-12
In Classic Nintendo Games Are NP-Hard (2012)My absolute favorite overview of this - the video goes over both the explanation of the spaces, but also how it relates to a sort of understanding of reality itself! [VIDEO]
sgrove on Hacker News · 2023-05
In Problems harder than NP-CompleteThis 10 minute video is a great introduction to the P = NP problem and computational complexity theory if you have no context. I've shown this to plenty of friends (including those outside of computer science). Essentially, "does being able to quickly recognize correct answers …
austinl on Hacker News · 2016-11
In The P=?NP Poll (2002) [pdf]
Summaries, classifications and recommendation records are from the HackerTube source dataset. Read about this library and its limitations.