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