CS:5340 Limits of Computation
Fall 2017

12:30-1:45 TTh 61 SH (Schaeffer Hall)

Sriram V. Pemmaraju
Office: 101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 1:30-2:30 M, 10:30-11:30 W, 2:00-3:00 F (and by appointment)

Course website: http://www.cs.uiowa.edu/~sriram/5340/fall17/
Department website: http://www.cs.uiowa.edu/

This course is a mathematical exploration of the limits of the power of computers and computation. Some of the questions we ask and attempt to answer are the following: are there problems that cannot be solved on any computer? What are some examples of these unsolvable problems? How do we prove that a problem is computationally unsolvable? If we place bounds on the resources (time and space) available to a computer, then what can be said about which problems can and cannot be solved on a computer? How do we show that as the resources (time and space) that a computer uses, are increased then the collection of problems that can be solved grows? How does the power of a computer change, if it has access to random bits? How does getting a limited amount of "advice" increase the power of a computer? What if the computer could interact in a limited way with a powerful advisor?

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 touch upon the surprising result that IP = PSPACE.

Syllabus document, Announcements, Homeworks and Exams, Weekly Topics, Online Resources

Homeworks and Exams


Weekly Topics