Understanding P vs. NP and the Computational Complexity Zoo 🧠

Hackerdashery #2

Inspired by the Complexity Zoo wiki: https://complexityzoo.uwaterloo.ca/Complexity_Zoo

For more advanced reading, I highly recommend Scott Aaronson's blog, Shtetl-Optimized: http://www.scottaaronson.com/blog/

-----

Retro-fabulous, cabinet-sized computers:

System/360: http://en.wikipedia.org/wiki/IBM_System/360

photo: "360-91-panel". Licensed under Public domain via Wikimedia Commons - http://commons.wikimedia.org/wiki/File:360-91-panel.jpg#mediaviewer/File:360-91-panel.jpg

PDP-8: http://en.wikipedia.org/wiki/PDP-8

photo: "PDP-8". Licensed under Public domain via Wikimedia Commons - http://commons.wikimedia.org/wiki/File:PDP-8.jpg#mediaviewer/File:PDP-8.jpg

-----

Protein folding illustration: "Protein folding schematic" by Tomixdf (talk) - Own work (Original text: “self-made”). Licensed under Public domain via Wikimedia Commons - http://commons.wikimedia.org/wiki/File:Protein_folding_schematic.png#mediaviewer/File:Protein_folding_schematic.png

P vs. NP opinion poll: http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf