Lecture 37

We revisit non deterministic Turing machines, and show their connection to the problems we have presented the in the last lecture. The observation leads to two complexity classes, P and NP.

We say that a problem is in P if it can be solved using a deterministic Turing machine in polynomial time.

We say that a problem is in NP if it can be solved using a non-deterministic Turing machine in polynomial time. The difference between the two machines is that one uses magic to select among possible next moves.

Reading: Algorithmics, Chapter 7.