22C:131 Limits of Computation

1:30-2:20 MWF, Room 213 MLH

Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 9-10 Tuesday, 11:30-12:30 Wednesday, and 2:30-3:30 Friday.

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 languages, Turing machines, undecidability, the time complexity classes such as P, NP, NP-complete, space complexity classes such as L and NL, the Cook-Levin theorem, reductions, poly-time heirarchy, randomized algorithms and randomized complexity classes such as BPP, approximation algorithms and hardness of approximation. Time permitting, we will also study interactive proofs.

Syllabus document, Information about TAs, Announcements, Homeworks and Exams, Lecture Notes, Online Resources

Information about TAs

The TA for this course is Rajiv Raman. Contact information and office hours for Rajiv are: 
		Office: 101K, MLH	
		Phone: 353-2542
		E-mail: rraman@cs.uiowa.edu
		URL: www.cs.uiowa.edu/~rraman/
		Office hours: TTh, 11:00-12:00

Homeworks and Exams

Announcements

Weekly Topics and some lecture notes

Online Resources