P vs. NP and the Computational Complexity Zoo
Channel:hackerdashery · Length:10:44 · Published:2014-08-26 · Views:3701963
Summary
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 recommends it
HN repeatedly recommends it as the best short, funny introduction to P vs. NP and complexity classes for people with no background.
This 10 minute video is a great introduction to the P = NP problem and computational complexity theory if you have no context. — HN, 2016
Computability & complexity theory · Recreational & visual math
Subtitles (excerpt)
Today I wanna talk about the deepest unanswered question in computer science, and, maybe in all of math. A problem called P vs. NP. And I wanna talk about how ideas from computing show up in the everyday world around us, and how problems as seemingly disparate as protein folding and making up crossword puzzles share a common core difficulty that turns out to be a lot like Sudoku, well, okay basically it is Sudoku. In 2000 the Clay institute offered 1 Million dollar each for the solutions to seven key problems in Math -- The Millennium Prize problems. These are profound and difficult problems and for most of them it takes a lot of specialized knowledge to even understand the question. Of the seven problems P vs. NP was both the most recently conceived -- in 1971, and by far the easiest one to understand and explain. And in March 2010 the Clay Institute awarded the first of its seven prizes for the solution to, yeah, not P vs. NP. So, what is the P vs. NP question? Well, back in the 1970s computer scientists were busily figuring out how to program their retro-fabulous, cabinet-sized computers to solve all the world's problems. Sometimes the first program anyone could think of for a particular problem would be unworkably slow
On Hacker News
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, 2023-05
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, 2017-12
> 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 m… — jlg23, 2017-06
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: [VIDEO] — d23, 2017-01
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?" [VIDEO] — austinl, 2016-11
Related videos
- Compiling and Optimizing Scripting Languages · Google TechTalks · 1:01:37
- Lucas Cavalcanti & Edward Wible - Exploring four hidden superpowers of Datomic · ClojureTV · 40:42
- Reverse emulating the NES to give it SUPER POWERS! · suckerpinch · 22:21
- RustLatam 2019 - Without Boats: Zero-Cost Async IO · Rust Programming Language · 32:24
- Conway's Game Of Life in APL · Dyalog · 7:47
- RSA ANIMATE: Changing Education Paradigms · Royal Society of Arts · 11:40
- Practical Common Lisp · Google TechTalks · 1:12:09
- Vectors | Chapter 1, Essence of linear algebra · 3Blue1Brown · 9:51
- Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich · Confreaks · 53:21
- But what is the Fourier Transform? A visual introduction. · 3Blue1Brown · 19:41
- But what is a neural network? | Deep learning chapter 1 · 3Blue1Brown · 18:40
- The Beauty of Bézier Curves · Freya Holmér · 24:25
- The Continuity of Splines · Freya Holmér · 1:13:50
- Jim Simons (full length interview) - Numberphile · Numberphile2 · 1:00:43
- But how does bitcoin actually work? · 3Blue1Brown · 25:15
- The essence of calculus · 3Blue1Brown · 17:04