This page, http://www.cs.uiowa.edu/~hzhang/c131/, is always under construction.

22C:131 Limits of Computation

Attention: Final exam in the final week, May 16, 2:15pm (Close Book and Notes, except 3 three sheets of letter-size papers)

Sample solutions to Homework 11 are available.

1:30-2:20 MWF, 118 MacLean Hall

Instructor: Hantao Zhang
Office: 201B MLH,
Email: hzhang@cs.uiowa.edu,
Tel: 353 2545
Office hours: MWF, 2:30-3:30pm
 Teaching assistant: Lu Bi
Office: B20J MLH,
Email: lu-bi@uiowa.edu,
Tel: 335 3650
Office hours: Tu., Th, 1:00-2pm

Goals and Objectives

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 the following topics:

  1. Computation models: Finite State Automata.
  2. Turing machines. Definitions and examples. Turing-decidable and Turing-recognizable languages.
  3. Enhancements of TMs: multi-tape TMs, non-deterministic TMs. Equivalence of these and the standard TM.
  4. Diagonalization. Acceptance problem is undecidable; Acceptance problem is recognizable; the complement of the Acceptance problem is unrecognizable.
  5. Reductions. Examples of other undecidable languages. Rice's theorem. Post's Correspondence Problem (PCP) is undecidable.
  6. Running time of Turing Machines. The classes P, NP, NP-hard, and NP-complete.
  7. Cook-Levin Theorem, some reductions.
  8. Space complexity, Savitch's Theorem, PSPACE. Quantified boolean formula satisfiability is PSPACE-complete. So is Generalized Geography.
  9. L (deterministic log space) and NL (non-deterministic log space). Log space reductions and NL-completeness. PATH is NL-complete.
  10. The space heirarchy and the time heirarchy theorems.

Prerequisite

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

Textbook

Introduction to the Theory of Computation (second edition) by Professor Michael Sipser. The book is available in Union Store and the latest errata can be found at http://www-math.mit.edu/~sipser/book.html

Homeworks (TEN homeworks, each counts for three percent of final score)

LATE-DUE HOMEWORK ARE NOT ACCEPTED. In general you will be better off turning in what you have on time rather than seeking extra time to complete your work. There will be no make-up exams in general and exceptions will be rare and only for students whose reasons are included in the University's policy on "Excused Absences from Examinations". Solutions will be provided on the course page for all graded work.

Exams (One midterm and one final exam)

Midterm on March 28 (30 percent of final score)

Final exam in the final week, May 16, 2:15pm (35 percent of final score)

Policies

For the policies on ACADEMIC DISHONESTY and PROCEDURE FOR COMPLAINT, see the Student Academic Handbook, http://www.clas.uiowa.edu/students/academic_handbook/index.shtml of the Colleage of Liberal Arts and Sciences.

The instructor of this course will follow the policies outlined at http://www.clas.uiowa.edu/faculty/teaching/new_policytemplate.shtml for ACCOMMODATIONS FOR DISABILITIES, UNDERSTANDING SEXUAL HARASSMENT, REACTING SAFELY TO SEVERE WEATHER.

Class Participation (5 percent of final score)

Lecture Notes

You are expected to study all the material in each chapter covered in the class even if that material is not explicitly discussed in class or in the homework. Material presented in class, but not in the book will not appear on tests.

The lecture notes are a supplement to the course textbook. They are supposed to help you understand the textbook material better, they are a replacement for neither the textbook nor the lecture itself.

Please only print the lecture notes on the day of the class as it's updating.


Hantao Zhang
Updated