hackertube.io

P vs. NP and the Computational Complexity Zoo

hackerdashery · explainer · Watch on YouTube

Computability & complexity theoryRecreational & visual math

What it is

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 Hacker News recommends it

HN repeatedly recommends it as the best short, funny introduction to P vs. NP and complexity classes for people with no background.

  • 4 people recommended it
  • 5 different months
  • 2 strong recommendations
  • first 2015, last 2026

What HN commenters said

  1. “There's a fantastic video I refer to every now and then”

    Revisited video explaining P vs NP

    sgrove, 2017-12 · Strong recommendation · in “Classic Nintendo Games Are NP-Hard (2012)”

  2. “This 10 minute video is a great introduction to the P = NP problem and computational complexity theory if you have no context.”

    Accessible 10 minute introduction to P vs NP

    austinl, 2016-11 · Recommendation · in “The P=?NP Poll (2002) [pdf]”

  3. “Very understandable even without any background on the topic”

    Understandable P vs NP explanation without background

    d23, 2017-01 · Recommendation · in “P vs. NP”

  4. “very funny and also provides a cursory glance at what lies beyond P vs NP”

    Funny short P vs NP overview and complexity zoo glance

    jlg23, 2017-06 · Recommendation · in “The asymmetry in storytelling between math and the other sciences”

Excerpts from Hacker News comments, linked to the originals. Summaries and labels were written by a language model from those comments.

Topics: p vs np, complexity classes, np-complete, complexity zoo, theory of computation

Also recommended by the same people