Skip to content
Hallway
0:00 / 0:00

#pvsnp#sat#satisfiability

What P vs NP is actually about

Polylog

123K subscribers • 1 video on Hallway

YouTube

Intermediate. Assumes working knowledge.

254K views2 years ago4 recommendations

Computer scienceComputation and complexityAlgorithmsMath for programmers

An explanation of how algorithms can be represented as logic circuits and encoded into satisfiability problems to explain P vs NP.

What if we could run algorithms backwards? We discuss how we could do this by turning algorithms into circuits and encoding those into satisfiability problems. We then explain how it all connects to P vs NP. Patreon: patreon.com/Polylog Website: polylog.cc #somepi Satisfiability Breaking RSA General reductions to SAT P vs NP Blog post: vasekrozhon.wordpress.com/2024/08/18/what-p-vs-np-is-actuall… Code for the animations: github.com/polylog-cs/np-completeness/ Blender clip: youtube.com/watch?v=qg1ckCkm8YI Richard Hladík: Script editor, animator Gabor Hollbeck: Video recording, video editor Václav Rozhoň: Writer, animator Václav Volhejn: Narrator, animator, script editor Thank you to our beta testers: Matěj, Honza, Filip Animations: manim, a Python library docs.manim.community/en/stable/ Color palette: Solarized ethanschoonover.com/solarized/ Music: Thannoid by Blue Dot Sessions Pictures: * Intel 8008: righto.com/2016/12/die-photos-and-analysis-of_24.html * Stephen Cook: heidelberg-laureate-forum.org/laureate/stephen-a-cook/ * Leonid Levin: cs.bu.edu/fac/Lnd/ * Richard Karp: icsi.berkeley.edu/icsi/people/karp * Mick Jagger, Keith Richards: Wikipedia * Hash function circuit: academia.edu/download/31149146/498-497.pdf

Why it's here

4 people recommend this

What people say. Highly recommended as an exceptionally clear, intuitive explanation of P vs NP through the lens of circuit reversibility and SAT.

nick_gon Hacker News • Recommends

On “What P vs. NP is about”

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

vasekrozhonon Hacker News • Recommends

On “What P vs. NP is about”

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 it into the video. The blog post you are discussing is such a blog post. So you should watch the video first and read the blog post only if you really liked the video and want to know more. :) 3) If you have any questions, I'll be happy to answer them! 1 link to this video
View on Hacker News

empath75on Hacker News • Recommends

On “Solving Sudoku in Python Packaging”

link to this 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 you need to do is codify the function in logic gates, including the output you want, and the ask a SAT solver to find the inputs that produce that output.
View on Hacker News

godelskion Hacker News • Recommends

On “How can AI researchers save energy? By going backward”

> 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 inverse. But, it might not always. So our function f(x)=mx+b is invertible, because we can write x = (f(x)-b)/m (well... m can't be 0), which provides a unique solution. Every x corresponds to a unique f(x). But if instead, we have the function f(x) = x^2, this is not true! x = sqrt(f(x)), and here e…
View on Hacker News

godelskion Hacker News • Recommends

On “I Verified My LinkedIn Identity. Here's What I Handed Over”

…s one thing when they're discovered independently but I'm pretty confident the computer scientists that pioneered hashes were quite familiar with the mathematics and nomenclature. > inverse computation would take an intractable amount of time. On a real side note I really like this explanation of P vs NP as it explicitly talks about reversibility. link to this video…
View on Hacker News