Steve Homer
Room 281 MCS, 353-8927, homer@bu.edu
Office Hours: Tuesday 3:30-4:30, Wednesday 1:30-2:30 in MCS 281
Teaching Fellow: Jiayu Zhang, jyz16@bu.edu
Office Hours: Wed 11-12am, Thu 3:30-4:30pm in MCS 135A
Home page : All information needed for this work required in this course can be found on the course home page at
http://www.cs.bu.edu/faculty/homer/332/Home.html
Text: Introduction to the Theory of Computation By Mike Sipser The preferred version is edition 3.
Recommended Texts: P, NP, and NP-Completeness: The Basics of Complexity Theory By Oded Goldreich, Cambridge University Press.
Computability and Complexity Theory by Homer and Selman,
Computers and Intractability: A Guide to NP-Completeness, by Garey and Johnson, Freeman Press.
Elements of the Theory of Computation by H. Lewis and C. Papdimitriou
Course Description:
We will begin with a brief review of the mathematical background needed for this course. This will include a quick review of sets, functions, decision problems and proofs techniques.
We study only TWO questions in this class.
-What is computation and what can and what cannot be computed ? (computability theory)
-What is efficient computation, which problems can be efficiently computed and which cannot? (computational complexity)
These two major topics of the course, computability theory and complexity theory, are covered in sections 2 and 3 of the Sipser textbook.
First we will study what can be computed, universal computation and Turing machines. We will cover deterministic and nondeterministic Turing machines, Church's thesis, computable (recursive) functions, universal machines, decidability. reductions, and a variety of unsolvable problems.
The second main topic will be complexity theory where we will consider resource bounded computations and what problems can be efficiently computed. The main topics will include time complexity, the classes P, NP, and PSPACE, and NP-completeness, and their relationships.
Grading: The way to master this course is to do problems. Problems will be stressed and some time taken in class and in section to discuss them. There will be about 5 problem sets, a midterm and a final.
The course grade will be based on homework - 30%, midterm - 30%, final - 40%.
Points will be taken off for late homework and incompletes will not be given.
Course Outline (very rough)
I. Week 1
Mathematical background - chapter 0 of text
II. Week 2-3
Definitions of computability and Turing machine computation - chapter 4
III. Weeks 3-4
Decidability and undecidability - chapter 5, section 1
IV. Week 5
Undecidable problems - chapter 4, section 2, and chapter 5
V. Week 6-7
Kolmogorov complexity - chapter 6, section 4, or some other advanced topic from chapter 6
VI. Weeks 8-9
Time complexity and NP - chapter 7
VII. Weeks 10
Space complexity - chapter 8
VIII. Weeks 11-12
Intractable problems - chapter 9
IX. Week 13
Interactive Proofs - chapter 10 or some other advanced topic from chapter 10
X. Week 14 - Finish up and review