Overview

We'll look at models of computers (eg. Turing machines) and see how they are used to measure the resources (time, space and others) required to solve problems. If we pick a model and a bound on one or more resources, we can define a complexity class (eg. P, NP, NC) to be the set of problems that can be solved in that model with the given resources. These classes give us a systematic way of understanding how efficiently problems can be solved.

In studying complexity theory, we learn about techniques that can be used to design efficient algorithms. We also learn how to identify those problems for which efficient solutions do not exist or are unlikely to exist. Such information is useful, because it often suggests how to modify our approach when faced with an intractable problem: for example, we might look for approximate solutions instead of exact solutions, or try to solve a special case of the problem that is sufficient for our needs.

The exact set of topics to be covered will depend partly on students' interests and background, but here is a tentative list of topics:

• Models of computation: various types of Turing Machines, Random Access Machines
• Definitions of some basic complexity classes (LOGSPACE, P, NP, coNP, PSPACE) & relationships between them
• Time & space hierarchy theorems
• Reductions, NP-completeness
• A brief introduction to randomized computation
• Parallel computation (circuits, Parallel Random Access Machines, NC, P-completeness)
• Approximating solutions to intractable problems (if time permits)

Important Dates

• Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1994. Errata.

Other References

• Ding-Zhu Du and Ker-I Ko, Theory of Computational Complexity, Wiley, 2000.
  
• Michael R. Garey and David S. Johnson, Computers and Intractability, W. H. Freeman, 1979.
  
• Joseph JáJá, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
• David S. Johnson, A catalog of complexity classes. In Handbook of Theoretical Computer Science, volume A, chapter 2. Elsevier, 1990.
• Richard M. Karp and Vijaya Ramachandran, Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science, volume A, chapter 17. Elsevier, 1990.
• Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.
• Uwe Schöning and Randall Pruim, Gems of Theoretical Computer Science, Springer, 1995.
• Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
• John H. Reif (editor), Synthesis of Parallel Algorithms, Morgan Kaufmann, 1993.
• John E. Savage, Models of Computation: Exploring the Power of Computing, Addison-Wesley, 1998.
• Michael Sipser, Introduction to the Theory of Computation, PWS, 1996.
• Peter van Emde Boas, Machine models and simulations. In Handbook of Theoretical Computer Science, volume A, chapter 1. Elsevier, 1990.

• Handout on big-O notation (modified version of some notes originally written by Faith Fich)
• Assignment 1
• Assignment 2
• Assignment 3
• Assignment 4

Updated May 2, 2001