22C:131 Limits of Computation

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

Required Legalese
This course is run by the College of Liberal Arts and Sciences. This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive the approval of the Dean of the College of Liberal Arts and Sciences. Details of the University policy of cross enrollments may be found online here.

Prerequisite
Undergraduate Algorithms (22C:31) or its equivalent.

Textbook
Michael Sipser, Introduction to the theory of computation, Second Edition, Published by Course Technology, ISBN 0534950973.

Grading
Plus/Minus grading will be used for the course. There are two components that will determine your grade.

• Homeworks: 50% 4-5 homeworks will be assigned during the semester. These will be posted on the class homepage and you will have two weeks for each homework.

• 2 Exams: 50% There will be one mid-term exam (worth 20% of your grade) and one final (worth 30% of your grade). The schedule for the exams is:

  Midterm	                March 9rd, Friday			Time and place TBA
  Final			May 9th, Wednesday			7:30-9:30 am (in 213 MLH)
  

  For the midterm, I would like to find a 2 hour slot on March 9th (possibly in the evening) that works for everyone. All exams will be open book/notes exams. The final will be cumulative,

Solutions will be provided on the course page for all graded work.

Teaching Assistant Information
The TA for the 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

Students with disabilities
I would like to hear from anyone who has a disability which may require seating modifications or testing accommodations or accommodations of other class requirements, so that appropriate arrangements may be made. Please contact me during my office hours.

Academic Dishonesty
Academic dishonesty will not be tolerated. Under no circumstances should you pass off someone else's work as your own. This also applies to code or other material that you might find on the internet. Note that we will routinely use available software systems for detecting software plagiarism, to test any suspicions we might have. If you are unclear about what constitutes academic dishonesty contact your professor or consult the printed policy in the Schedule of Courses and the CLAS Bulletin (online version). We do want students to talk to each other about concepts and ideas that relate to the class. However, it is important to ensure that these discussions do not lead to the actual exchange of written material.

Student Complaints
If you have any complaints or concerns about how the course is being conducted by me or by the TAs please feel free to talk to me. You are also welcome to get in touch the the Computer Science department chair, Prof. Jim Cremer (cremer@cs.uiowa.edu, 319-335-1713, 14D McLean Hall). Consult the college policy on Student Complaints Concerning Faculty Actions (online version) for more information.

List of Topics:

1. Turing machines. Definitions and examples. Turing-decidable and Turing-recognizable languages.
2. Enhancements of TMs: multi-tape TMs, non-deterministic TMs. Equivalence of these and the standard TM.
3. Diagonalization. Acceptance problem is undecidable; Acceptance problem is recognizable; the complement of the Acceptance problem is unrecognizable.
4. Reductions. Examples of other undecidable languages. Rice's theorem. Post's Correspondence Problem (PCP) is undecidable.
5. Running time of Turing Machines. The classes P, NP, NP-hard, and NP-complete.
6. Cook-Levin Theorem, some reductions.
7. Space complexity, Savitch's Theorem, PSPACE. Quantified boolean formula satisfiability is PSPACE-complete. So is Generalized Geography.
8. L (deterministic log space) and NL (non-deterministic log space). Log space reductions and NL-completeness. PATH is NL-complete.
9. RL (randomized log space). Using random walks to show that UPATH (undirected path) is in RL. SL and a mention of Omer Reingold's result showin that UPATH is is L and therefore SL = L.
10. The space heirarchy and the time heirarchy theorems.
11. Randomized algorithms and randomized complexity classes. Randomized algorithms for primality testing.
12. Approximation algorithms. The PCP theorem (statement) and its implications to hardness of approxitmation.