What P vs NP is actually about

Support us on Patreon: http://patreon.com/polylog 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. #somepi 0:48 Satisfiability 2:15 Breaking RSA 8:46 General reductions to SAT 12:03 P vs NP Blog post: https://vasekrozhon.wordpress.com/2024/08/18/what-p-vs-np-is-actually-about/ Code for the animations: https://github.com/polylog-cs/np-completeness/ Blender clip: https://www.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 https://docs.manim.community/en/stable/ Color palette: Solarized https://ethanschoonover.com/solarized/ Music: Thannoid by Blue Dot Sessions Pictures: * Intel 8008: https://www.righto.com/2016/12/die-photos-and-analysis-of_24.html * Stephen Cook: https://www.heidelberg-laureate-forum.org/laureate/stephen-a-cook/ * Leonid Levin: https://www.cs.bu.edu/fac/Lnd/ * Richard Karp: https://www.icsi.berkeley.edu/icsi/people/karp * Mick Jagger, Keith Richards: Wikipedia * Hash function circuit: https://www.academia.edu/download/31149146/498-497.pdf