|
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://cs-www.bu.edu/faculty/homer/535/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
-----------------------------------------------------------------------------------------
This course 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 theories we learn how to prove that hard 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 first 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 majority of the class will be spent studying the fundamentals of complexity theory. 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 course grade will be based on homework - 60%, exams - 40% (in class midterm 0% and final 40%).
Points will be taken off for late homework and incompletes will not be given.