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
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
- Homework 1. Due on 2/12, in class.
- Homework 2: Problems 5.13, 5.15, 5.17, 5.33, 5.35.
Due on 3/5.
- Homework 1 Solution along with
Problem Session 1.
- Notes from Problem Session 2.
- Homework 2 Solution
- About the midterm
- Homework 3: Problems 8.11, 8.15, 8.16, 8.19, 8.23.
Due on 4/11. Deadline extended to 4/13. Also see
these hints
for Problems 8.15 and 8.23.
- Homework 4: 8.26, 9.12, 9.13, 9.14, 10.11, 10.19, 10.20, 10.22.
Solve any 5 of these problems for the homework. Due at finals time,
Wednesday, May 9th.
- Hints for Homework 4. Right now this only contains a hint for Problem 8.26.
More hints will be added by Monday 5/7.
- Week 1: 1/15-1/19: Turing machines. Definitions and examples. Turing-decidable and Turing-recognizable languages.
- Week 2: 1/22-1/26: Variants of TMs: multi-tape TMs, non-deterministic TMs and the equivalence between these and the standard TM.
- Week 3: 1/29-2/2: Diagonalization, countable and uncountable sets,
the Halting problem.
- Week 4: 2/5-2/9: Undecidability of the Halting problem.
- Week 5: 2/12-2/16: Post Correspondence Problem is undecidable.
Using reductions to show other problems undecidable.
- Week 6: 2/19-2/23: Time complexity classes: P and NP.
- Week 7: 2/26-3/2: NP-hardness, NP-completeness, The Cook-Levin Theorem: NP-completeness of SAT.
- Week 8: 3/5-3/9: Using polynomial time reductions to prove other problems NP-hard.
- Week 9: 3/19-3/23: Space complexity classes, PSPACE and NPSPACE, PSPACE-completeness.
- Week 10: 3/26-3/30: Proof that TQBF is PSPACE-complete, Logspace complexity classes: L and NL
- Week 11: 4/2-4/6: PATH is in NL, but not known to be in L, NL-completeness of PATH
- Week 12: 4/9-4/13: NL = coNL. The space and time heirarchy theorems.