CS 535 Home Page

CS 535: Complexity Theory - Fall 2010

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:


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 (

Notes on Complexity Theory by Leonid Levin (

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.