P vs. NP and the Computational Complexity Zoo - YouTube
Erik Demaine introduces NP-completeness, illustrating how to prove a problem's difficulty through reductions. The lecture covers diverse examples, ranging from theoretical satisfiability problems to the computational complexity of games like Super Mario Brothers.
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…
saved by
related reading
- P versus NP problem - Wikipediaen.wikipedia.org
- P vs. NP for Dummiesscottaaronson.blog
- pnp.pdfscottaaronson.com
- NP-completeness - Wikipediaen.wikipedia.org
- P vs NP and its application to zero knowledge proofs | RareSkillsrareskills.io
- Reasons to believescottaaronson.blog
- What P vs NP is actually about – Vasek Rozhon's blogvasekrozhon.wordpress.com
- Computational Complexity Theory (Stanford Encyclopedia of Philosophy)plato.stanford.edu
- Complexity class - Wikipediaen.wikipedia.org
- Shtetl-Optimized >> Blog Archive >> The First Law of Complexodynamicsscottaaronson.blog
- NP (complexity) - Wikipediaen.wikipedia.org
- aaronson-philosophy.pdfcs.princeton.edu