11:00-12:15 TTh, Room E203 CB
Instructor:
Sriram V. Pemmaraju
101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: M 11:30-1:00, W 1:00-2:30 and by appointment
This course is a mathematical exploration of the limits of the power of computers. Some of the questions we ask and attempt to answer are the following. Are there problems that cannot be solved on any computer? How does one determine if a given problem can or cannot be computationally solved? If we place bounds on the resources (time and space) available to a computer, then what can be said about which problems can and which problems cannot be solved on a computer? How does the power of a computer change, if it has access to random bits? What happens when we relax the notion of solving a problem to "approximately" solving a problem - does this fundamentally change which problems can and which problems cannot be solved on a computer?
In attempting to answer these questions we will study models of computation such as Turing machines and Boolean circuits, time complexity classes such as P, NP, NP-complete and those in the polynomial hierarchy, space complexity classes such as PSPACE, L and NL, and randomized complexity classes such as RP and BPP. We will also study interactive proofs and the corresponding complexity class IP and the surprising result that IP = PSPACE. Time permitting, we will also study the PCP theorem and hardness of approximation.
Syllabus document, Information about TAs, Announcements, Homeworks and Exams, Lecture Notes, Online Resources
You will not be responsible for Section 1.5.2 (on Godel's Theorem) and Section 1.7 (on an efficient Universal TM). You should read the rest of the chapter carefully. I skipped time-constructible functions (Page 16) and will introduce these when we get to Chapter 3.
I skipped the reductions: SAT to 0/1 IPROG (Theorem 2.16) and SAT to dHAMPATH (Theorem 2.17), but I do expect you to read and understand these proofs. More generally, you are responsible for reading the entire chapter carefully.