22C:131 Limits of Computation
1:30-2:20 MWF, Room 213 MLH
Sriram V. Pemmaraju
101G MLH, firstname.lastname@example.org, 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
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.
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: 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
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.
- Reading for Week 1 (1/15-1/19): Pages 137-142 on intro. to Turing
- Reading for Week 2 (1/22-1/26): All of Chapter 3.
- Reading for Week 3 (1/29-2/2): Section 4.2 on the Halting problem,
diagonalization, and undecidability.
- 2/5: The class TA Rajiv Raman will run a problem solving session
during 5-6:30 pm on Wednesday, 2/7.
- Reading for Week 4 (2/5-2/9): Section 4.2 on the Halting problem.
- Reading for Week 5 (2/12-2/16): Section 5.2 on the PCP.
- Reading for Week 6 (2/19-2/23): Sections 7.1 and 7.2.
- 2/28: The class TA Rajiv Raman will run a problem solving session
during 5-6 pm in B13 MLH on Wednesday, 2/28.
- 3/6: Midterm will be during 5-7 pm on Friday, March 9th in
- 4/9: Homework 3 extended deadline: due on Friday, 4/13.
- 5/3: Here are scores and tentative letter grades.
Please report any errors you find.
- 5/5: Here is some information about
- 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.