28: Efficiency, P and NP (47min)

Foundations of Computer Science, Rensselaer Fall 2020.

Professor Malik Magdon-Ismail talks about efficiency and discusses the problems in P (polynomial time) and NP (nondeterministic polynomial time). We demonstrate how polynomial time is a robust definition of "fast" because it is architecture independent. This is the last lecture. Enjoy your next course: Algorithms! Always take the time and effort to prove your program works fully correctly all the time, others rely on it.

This is the twenty-eighth lecture in a "theory" course focusing on discrete math and the foundations of computing: what can we compute and what can't we compute.

Level of the course: Sophomore Computer Science or related major.

Material is from Chapter 28 of "Discrete Mathematics and Computing", dmc-book.com.