Skip to content
Hallway
0:00 / 0:00

#pvsnp#computationalcomplexity#complexityzoo

P vs. NP and the Computational Complexity Zoo

hackerdashery

43K subscribers • 1 video on Hallway

YouTube
  • Recommended by 7 people: 4 on Hacker News, 1 on Lobsters and 2 in engineering communities.
  • A classic. People kept recommending it from 2015 to 2023.

Beginner. No background in the topic needed.

3.6M views12 years ago7 recommendations

Computer scienceComputation and complexityAlgorithms

An animated introduction to the P vs. NP problem and the broader landscape of computational complexity classes.

Hackerdashery #2 Inspired by the Complexity Zoo wiki: complexityzoo.uwaterloo.ca/Complexity_Zoo For more advanced reading, I highly recommend Scott Aaronson's blog, Shtetl-Optimized: scottaaronson.com/blog/ ----- Retro-fabulous, cabinet-sized computers: System/360: en.wikipedia.org/wiki/IBM_System/360 photo: "360-91-panel". Licensed under Public domain via Wikimedia Commons - commons.wikimedia.org/wiki/File:360-91-panel.jpg#mediaviewer… PDP-8: en.wikipedia.org/wiki/PDP-8 photo: "PDP-8". Licensed under Public domain via Wikimedia Commons - commons.wikimedia.org/wiki/File:PDP-8.jpg#mediaviewer/File:P… ----- Protein folding illustration: "Protein folding schematic" by Tomixdf (talk) - Own work (Original text: “self-made”). Licensed under Public domain via Wikimedia Commons - commons.wikimedia.org/wiki/File:Protein_folding_schematic.pn… P vs. NP opinion poll: cs.umd.edu/~gasarch/papers/poll2012.pdf

Why it's here

7 people recommend this

What people say. Highly recommended as an exceptionally clear, accessible, and engaging introduction to computational complexity theory for beginners.

Moments people linked to

u/te-xin r/compsci • Recommends

P vs. NP and the Computational Complexity Zoo
219View on Reddit

sgroveon Hacker News • Recommends

On “Classic Nintendo Games Are NP-Hard (2012)”

There's a fantastic video I refer to every now and then if I'm a bit unsure about it, definitely recommend it - link to this video
View on Hacker News

sgroveon Hacker News • Recommends

On “Problems harder than NP-Complete”

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! link to this video
View on Hacker News

jtobinon Lobsters • Recommends

P vs. NP and the Computational Complexity Zoo (2014)
6View on Lobsters

austinlon Hacker News • Recommends

On “The P=?NP Poll (2002) [pdf]”

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?" link to this video
View on Hacker News

d23on Hacker News • Recommends

On “P vs. NP”

A guy at a company I used to work for made a great video on this. Very understandable even without any background on the topic: link to this video
View on Hacker News

jlg23on Hacker News • Recommends

On “The asymmetry in storytelling between math and the other sciences”

…ined 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: link to this video (10 min)…
View on Hacker News

u/Nekerin r/compsci • Recommends

P vs. NP and the Computational Complexity Zoo
1View on Reddit

u/justinba1010in r/compsci • Mentions

On “Intuition Behind P=NP ?”

…s there is an inherent difficulty to solving some problems, and recognizing the elegance and beauty in the solution. Edit: I wanted to answer this because it's one of my favorite problems in CS. And NP stands for polynomial time for a nondeterministic machine, which means if a machine didn't have to take one step at a time(oversimplifying it). [video [video [video…
71View on Reddit

u/britcruisein r/compsci • Mentions

On “I spent a long time making a P vs. NP video that is grounded in concrete terms & visuals - no hand waving.”

thank you so much, I'm glad to hear it because I was so frustrated with the existing ones including this (link to this video which youtube search algorithm likes more :)
19View on Reddit

u/claytonkbin r/compsci • Mentions

On “P vs NP problem insights?”

PIN codes are probably the wrong way to think about P v. NP because PIN codes are a challenge problem (think game theory, not algorithms). There is a field of complexity theory that deals with challenge-based algorithms (aka "interactive proofs") and they do have connections to P v. NP but they are also *really* complicated stuff. I'll give an ELI5 of PvNP with some abuse of notation/jargon for the purpose of simplification: Consider a black-box deterministic function f(x). As x becomes very large, f(x) requires time not more than x^2 in order to return a result. We call this "polynomial time" because the running-time of f() is bounded by some polynomial function of its input. The polynomi…
9View on Reddit

u/Blautkakin r/compsci • Mentions

On “What algorithm would revolutionize the industry if it could be discovered?”

ELI(slightly more than 5): link to this video About 10 min, so you probably won't fully understand, but it is a great introduction, and you get an idea of it's importance.
8View on Reddit

u/fewdeain r/compsci • Mentions

On “P vs NP”

This video really cleared some things up for me.
4View on Reddit

u/Kamikaze28in r/compsci • Mentions

On “In the Futurama episode "Put your head on my shoulders", the problem of P versus NP is clearly defined in two books in a small closet.”

link to this video
3View on Reddit

u/aysz88in r/compsci • Mentions

On “Polynomial time?”

You can take inspiration from a few existing popsci-style explainers - these have 5-7-digit viewcounts, and you may want to look at not only the videos, but the comments below them for common pitfalls. * link to this video is probably the most popular one, covering both the technical explanation (of what the problem is) to the profound implications (why P=?NP gets referenced a lot) * link to this video * link to this video * link to this video
3View on Reddit

ColinWrighton Hacker News • Mentions

On “Integer Factoring via Graph Three Colouring”

Because Graph Three Colouring01 is NP-Complete23 we can use it to solve any NP problem. Integer factoring is an NP problem4 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 link to this video 4 link
View on Hacker News