---

Formal Languages and Computability
INF3 Semester

Lecture 14

---

Topics

A natural variation on this class is obtained by considering the class of decision problems that can be solved in polynomial time by nondeterministic Turing machines. The resulting complexity class is called NP, and will be the topic of the last two lectures of the course.

Clearly, P is included in NP (why?), but is the converse true? The answer to this question, usually dubbed as "P versus NP" problem, is as yet unknown, and is one of the main open problems in science as a whole. This problem is also one the Millennium Prize Problems announced by the Clay Mathematics Institute, and carries a $1 million reward. (You might wish to read the popular article Million-Dollar Minesweeper by Ian Stewart for further information.)

During this lecture we shall also see how we can formally characterize the "hardest problems" in the class NP. These problems are called NP-complete, and abound in many forms of scientific endeavour. Informally, a problem is NP-complete if it is in the class NP, and the existence of a polynomial time deterministic solution for it would yield polynomial time deterministic algorithms for all of the problems in NP.

Time and Location

Reading Material

• Material in pages 241-253 of Sipser's book.
• As supplementary reading material, I strongly recommend pp. 91-117 in Computers Ltd.: What They Really Can t Do (Oxford University Press) by David Harel. (These are available for photocopying from the course folder for the NB course on INF5.)

Exercises

• Work out exercise 7.7(*) in Sipser's book.
• (*) Answer the questions on slide number 10 for the lecture.
• Work out exercises 7.11, 7.17 and 7.29 in Sipser's book.
• Work out the reduction on slide number 9 for the lecture.