|
Steve Homer
Office: 281 MCS Phone: 353-3927
Office Hours: Tuesday, 12:00 - 1:30 and Thursday, 11:00-12:30 and by appointment.
Class Home Page: http://www.cs.bu.edu/faculty/homer/535-10/Home.html
-----------------------------------------------------------------------------------------
Required Text: Computability and Complexity Theory by S. Homer and A. Selman, Springer
-----------------------------------------------------------------------------------------
Recommended Texts and Notes:
Complexity Theory Notes by Jin-Yi Cai
Structural Complexity Theory I, by Balcazar, Diaz and Gabarro
Computers and Intractability by Garey and Johnson
Complexity Theory by C. Papadimitriou
Notes on Complexity Theory by Gacs and Lovasz (http://www.cs.bu.edu/fac/gacs/papers/lovasz-notes.ps.gz)
Notes on Complexity Theory by Leonid Levin (http://www.cs.bu.edu/fac/lnd/toc/)
Intro. to Theory of Computation by Sipser
P, NP, and NP-Completeness: The Basics of Computational Complexity by Oded Goldreich
Computational Complexity: A Modern Approach By S. Arora and B. Barak
-----------------------------------------------------------------------------------------
CS 535 studies computation and its limits. In computability we consider the border between computable and non-computable functions and the properties of non-computable problems. In complexity theory we consider the extent and the limits of efficient computation. In both areas we learn how to prove that hard computational problems exist, to classify them, and to show that they arise naturally and often.
We will begin by briefly reviewing some background in elementary set theory and discrete math. Then we will introduce computation and define the Turing machine model and study both complexity and computability using this model.
The majority of the class will be spent studying the fundamentals of complexity theory, computing with limited resources. Bounding the time and space of computations will be considered first. Then we will focus on resource bounded nondeterministic computation where the class NP in particular will be the focus of much of the class. Reducibilities between various problems and properties of reductions will be emphasized. Finally, we will consider other types of computational resources including randomness in computing, and the power of interactive proof systems. Properties of computations using all of these measures will be explored as time allows.
The last month or so of the class will be used to study computations without any resource limits, that is, computability theory. We will consider different machine models including various types of Turing machines, pointer machines and other random access machines. The focus will be on undecidability, and reductions between undecidable problems.
-----------------------------------------------------------------------------------------
The course grade will be based on homework - 50% (probably 7 assignments), exams - 50% (midterm 10% and final 40%).
Points may be taken off for late homework and incompletes will not be given.