hackertube.io

What P vs NP is actually about

Polylog · explainer · Watch on YouTube

Computability & complexity theoryAlgorithms & data structures

What it is

Polylog explains how algorithms can be turned into circuits and encoded as satisfiability problems, which lets you effectively run them backwards. It uses this to motivate breaking RSA, general reductions to SAT, and what P vs NP is really asking.

Why Hacker News recommends it

Recommended as an intuitive, animated explanation of P vs NP framed around reversing computation.

  • 4 people recommended it
  • 3 different months
  • 1 strong recommendations
  • first 2024, last 2026

What HN commenters said

  1. “I would highly recommend giving it a watch”

    Really enjoyed it; good for newcomers to P vs NP ramifications.

    nick_g, 2024-10 · Strong recommendation · in “What P vs. NP is about”

  2. “We recently made a video about an underrated take on P vs NP.”

    Author's high-effort video on an underrated take on P vs NP.

    vasekrozhon, 2024-10 · Recommendation · in “What P vs. NP is about”

  3. “This video I think makes it obvious why that's true in a pretty intuitive way.”

    Makes intuitive why SAT inverts any function.

    empath75, 2024-10 · Recommendation · in “Solving Sudoku in Python Packaging”

  4. “Polylog actually has a really good video and will make the connection to P vs NP”

    Connects computation directionality to P vs NP via circuits.

    godelski, 2025-06 · Recommendation · in “How can AI researchers save energy? By going backward”

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, sat, np-completeness, circuits, complexity theory

Also recommended by the same people