What P vs NP is actually about
Channel:Polylog · Length:17:57 · Published:2024-08-19 · Views:278162
Summary
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 HN recommends it
Recommended as an intuitive, animated explanation of P vs NP framed around reversing computation.
I would highly recommend giving it a watch — HN, 2024
Algorithms & data structures · Computability & complexity theory
Subtitles (excerpt)
Ever wonder if we could run computers backwards? Today we'll be looking at the most famous problem in computer science, P vs NP, from this unusual angle. By the end of this video, you'll understand why the P vs NP question is ultimately about whether we can invert algorithms. First, we'll meet satisfiability, or SAT for short, a kind of superhero among algorithmic problems. We know literally thousands of equivalent definitions of it, and we still have no idea how to solve it. Next, we'll break a famous cipher by building a multiplication circuit and using SAT to run it backwards. Finally, we'll see how the idea of inverting algorithms connects to the most important question in computer science, P versus NP. Our story starts with the satisfiability problem, also known as SAT. This is an incredibly powerful problem. We'll see that, if we could solve it efficiently, we could use it to reverse any algorithm. Let's see what the problem is about. We're given a bunch of boolean variables, meaning each can be set to either true or false. But since I'm a programmer, I'll write 1 and 0 instead. We're also given a bunch of logical constraints on those variables that have to be satisfied. In the general SAT problem, a constraint can be an arbitrarily
On Hacker News
Despite being mentioned throughout the post, I don't see a link to the video in question. I saw it when it was posted a few weeks back and really enjoyed it. I would highly recommend giving it a watch, especially if the ramifications of P vs NP are new to you [1] [1] [VIDEO] — nick_g, 2024-10
Yeah that's a good addition. I think often the words we use can really make things more confusing. Like I hate when people say invertible but in reference to a function that isn't bijective. Why not say reversible? (No complaints with the convention of image/preimage) Which it's very similar to the problem created by saying "one way". It just isn't one way. Going the other direction is perfectly … — godelski, 2026-02
> What does it mean for computation to have a direction? Actually, all computation has a directionality! This is actually a subject that I get really excited about ^__^ Think about this, we have a function f, with input x, and output y. f(x) -> y We'd even use that notation! This is our direction. Now, the reverse actually gets a bit tricky. If the reverse is straightforward, our function has an … — godelski, 2025-06
Hi, the author of the blog post here. 1) With others, I work on high-effort Youtube videos, our channel's called Polylog. We recently made a video about an underrated take on P vs NP. [1] 2) After working on the high-effort video, I always write a low-effort stream-of-consiousness-style very-much-unedited blog post where I clarify some details or explain some more esoteric stuff that did not make… — vasekrozhon, 2024-10
[VIDEO] This video I think makes it obvious why that's true in a pretty intuitive way. I posted it a few days ago as a link and it never got traction. SAT is the equivalent of being able to find the inverse of _any_ function, because you can describe any function with logic gates (for obvious reasons), and any collection of logic gates that describes a function is equivalent to a SAT problem. All… — empath75, 2024-10
Related videos
- This high-speed rail project is a warning for the US · Vox · 8:25
- Animated Voting Methods · Unify The Vote · 6:18
- How our voting system (and IRV) betrays your favourite candidate · The Center for Election Science · 3:34
- Harder Drive: Hard drives we didn't want or need · suckerpinch · 36:46
- Professional SMT Soldering: Hand Soldering Techniques - Surface Mount · John Gammell · 3:19
- Bayes theorem, the geometry of changing beliefs · 3Blue1Brown · 15:11
- Why do prime numbers make these spirals? | Dirichlet’s theorem and pi approximations · 3Blue1Brown · 22:20
- John Cleese vs Extremism · eroosters · 2:12
- The Future of War, and How It Affects YOU (Multi-Domain Operations) - Smarter Every Day 211 · SmarterEveryDay · 28:11
- Lecture 1 | The Theoretical Minimum · Stanford · 1:46:33
- Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich · Confreaks · 53:21
- CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step” · CppCon · 59:33
- The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever? · Reducible · 28:23
- Modern Dictionaries by Raymond Hettinger · SF Python · 1:07:41
- 28c3: The Science of Insecurity · 28c3 · 59:23
- "Propositions as Types" by Philip Wadler · Strange Loop Conference · 42:43