22C:131 Limits of Computation
1:30-2:20 MWF, Room 205 MLH
Sriram V. Pemmaraju
101G MLH, email@example.com, 319-353-2956
Office Hours: 9-10 Tuesday, 11:30-12:30 Wednesday, and 9-10 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
If we place bounds on the resources (time and space) available to a
computer, then what say 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 classes of problems P, NP, NP-complete,
the Cook-Levin theorem, reductions, randomized algorithms and
randomized complexity classes such as BPP, approximation algorithms and
hardness of approximation.
Time permitting, we will also study interactive proofs.
Information about TAs,
Homeworks and Exams,
The TA for this course is Rajiv Raman.
Contact information and office hours for Rajiv are:
Office: 101K, MLH
Office hours: Wednesday and Friday, 2:30-3:30
- Homework 1. Due on Monday, 2/20.
- For Homework 2, solve 5.15, 5.19, 7.18, 7.27, and 7.39. All problem
numbers refer to Sipser, 2nd ed. Due on Wednesday, March 8th.
Here is a partital mapping between 2nd ed and 1st ed of Sipser,
5.15 -> 5.15, 7.18 -> 7.18, 7.27 -> 7.34, 7.39 -> 7.32.
Problem 5.19 is this: In the Silly Post Correspondence Problem,
SPCP, in each pair the top string has the same length as the bottom
string. Show that SPCP is decidable.
- Solution to midterm exam.
- Homework 3. Due on Wednesday, 4/5.
Updated to give mapping from Edition 2 to Edition 1 and one problem
is replaced by another. Here are some hints for
two of the problems.
- Homework 4. Due on Monday, 5/8.
- Week 1: 1/17-1/20: Turing machines. Definitions and examples. Turing-decidable and Turing-recognizable languages.
- Week 2: 1/23-1/27: Enhancements of TMs: multi-tape TMs, non-deterministic TMs. Equivalence of these and the standard TM.
- Week 3: 1/30-2/3: Diagonalization. Acceptance problem is undecidable; Acceptance problem is
recognizable; the complement of the Acceptance problem is unrecognizable.
- Week 4: 2/6-2/10: Reductions. Examples of other undecidable languages.
Rice's theorem. Post's Correspondence Problem (PCP) is undecidable.
- Week 5: 2/13-2/17: Running time of Turing Machines.
The classes P, NP, NP-hard, and NP-complete.
- Week 6: 2/20-2/24: Cook-Levin Theorem, some reductions.
- Week 7: 2/27-3/3: Space complexity, Savitch's Theorem, PSPACE.
- Week 8: 3/6-3/10: Quantified boolean formula satisfiability
is PSPACE-complete. So is Generalized Geography.
- Week 9: 3/13-3/17: L (deterministic log space) and NL
(non-deterministic log space). Log space reductions and NL-completeness.
PATH is NL-complete.
- Week 10: 3/27-3/31: RL (randomized log space).
Using random walks to show that UPATH (undirected path) is in RL.
and a mention of Omer Reingold's result showin that UPATH is is L and therefore SL = L.
- Week 11: 4/3-4/7: The space heirarchy and the
time heirarchy theorems.
- Week 12: 4/10-4/14: Randomized algorithms and randomized
complexity classes. Randomized algorithms for primality testing.