Unit 7: Limits of Computation

Resources

Complexity classes of problems

In computational complexity theory problems are classified into classes according to the algorithmic complexity for solving them. Confusion often arises due to the fact that naming of these classes are not intuitive, and even misleading. For instance, many consider that the complexity class "NP" stands for "non-polynomial time" when it actually stands for "non-deterministic polynomial time".

Complexity classes of problems

https://thomasvilhena.com/2019/08/complexity-classes-of-problems

Complexity classes of problems

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".

P vs. NP and the Computational Complexity Zoo

https://www.youtube.com/watch?v=YX40hbAHx3s

P vs. NP and the Computational Complexity Zoo

Beyond Computation: The P vs NP Problem - Michael Sipser

Beyond Computation: The P vs NP Problem - Michael Sipser

https://www.youtube.com/watch?v=msp2y_Y5MLE

Beyond Computation: The P vs NP Problem - Michael Sipser

MIT 6.006 Introduction to Algorithms, Spring 2020 Instructor: Erik Demaine View the complete course: https://ocw.mit.edu/6-006S20 YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY This lecture discusses computational complexity and introduces terminology: P, NP, EXP, R. These terms are applied to the concepts of hardness and completeness. The lecture ends with discussion on reductions.

https://www.youtube.com/watch?v=JbafQJx1CIA

19. Complexity

16. Complexity: P, NP, NP-completeness, Reductions

16. Complexity: P, NP, NP-completeness, Reductions

https://www.youtube.com/watch?v=eHZifpgyH_4

16. Complexity: P, NP, NP-completeness, Reductions

Share your videos with friends, family, and the world

https://www.youtube.com/playlist?list=PLlwsleWT767dnN25K_QgvdKkovK_t4K6-

P vs NP