Support us on Patreon: [ Ссылка ]
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: [ Ссылка ]
Code for the animations: [ Ссылка ]
Blender clip: [ Ссылка ]
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 [ Ссылка ]
Color palette: Solarized [ Ссылка ]
Music: Thannoid by Blue Dot Sessions
Pictures:
* Intel 8008: [ Ссылка ]
* Stephen Cook: [ Ссылка ]
* Leonid Levin: [ Ссылка ]
* Richard Karp: [ Ссылка ]
* Mick Jagger, Keith Richards: Wikipedia
* Hash function circuit: [ Ссылка ]
