4 HN users recommended this explainer5 months2015–2026score 6
Years with an HN recommendation, 2007–2026
HN repeatedly recommends it as the best short, funny introduction to P vs. NP and complexity classes for people with no background.
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.
“This 10 minute video is a great introduction to the P = NP problem and computational complexity theory if you have no context.” (HN, 2016)
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! [this video]
Overview of complexity classes and relation to reality
This 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 mean there's also a quick way to find them?" [this video]
> I would guess the P!=NP proof would be an example. Unfortunately, it doesn't have any easy description that the average person would understand. "Hard. Really hard. Don't be ridiculous.". Now backtrack 2 small examples on paper. Oh, look, the number of steps here grow, but these grow even faster! Especially mathematics when explained to a layperson so much depends on the language used. If one manages to keep the rest of the complexity zoo[1] out of the explanation and invests time into very basic examples, a lot things can be explained that otherwise the average person would not understand. [1] [link] EDIT: Looking for a video I stumbled upon last week that had a very nice, short explanation of P vs NP (which I did not find again), I found this one: Not lay-person simple, but very funny and also provides a cursory glance at what lies beyond P vs NP, i.e. the complexity zoo: [this video] (10 min)
Funny short P vs NP overview and complexity zoo glance
Because Graph Three Colouring[0][1] is NP-Complete[2][3] we can use it to solve any NP problem. Integer factoring is an NP problem[4] so we should be able to factor integers by using Graph Three Colouring. This post shows one way of doing that, and explains the techniques used to show directly that Graph Three Colouring is NP-Complete. [0] [link] [1] [link] [2] [link] [3] [this video] [4] [link]
I took a class from Gasarch in the 80's at UMD. He's a freaky smart guy! I swear to God (and have said before [1]): He wore a t-shirt that said: "P=NP? I don't know, and I don't care!" How times have changed! [1] HN discussion: [link] of Scott Aaronson's article "My 116-page survey article on P vs. NP: better late than never": [link] Also: P vs. NP and the Computational Complexity Zoo [this video]
I have taken algorithms courses. This video explains in detail: [this video] In short, P means Polynomial time (i.e. markets can solve computation problems efficiently) and NP means Non-Deterministic Polynomial time (i.e. markets can verify solutions of computation problems efficiently but solutions are found by luck). If P != NP, it means luck CANNOT be engineered and markets are competitive.
Video list and Hacker News comment labels from HackerTube (prompted by @karpathy), released under ODC-By 1.0, built on the open-index/hacker-news archive. Hacker News data is provided by Y Combinator; comments remain the work of their authors. Video titles, channel names and thumbnails belong to their creators and are shown via YouTube. HackerTube Watch is an unofficial edition. Data export of 2026-10-31.
Plays via YouTube's privacy-enhanced embed
8 Hacker News comments
From the HN archive; up to 20 kept per video, favoring different commenters. Recommendations first.
Read more
Citations, criticism and jokes