COSC6115, Winter 2001

## COSC6115W: Computational Complexity Winter 2001 ## General Information

Instructor: Eric Ruppert
Office: CCB 344
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: MWF14:30 in Bethune College, room 228
Office Hours: After lectures, or by appointment

### Overview

This course is intended to give graduate students a solid grasp of the fundamentals of complexity theory, which is an important part of the foundations of the entire field of computer science.

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)
Most of the material will be selected from the textbook, listed below, which is well-written and provides an excellent introduction to the subject.

### Important Dates

 Monday, February 26 First day of winter term classes Wednesday, March 21 Assignment 1 due Monday, March 26 No class Monday, April 9 Assignment 2 due Friday, April 13 Good Friday (no class) Monday, April 30 Assignment 3 due Friday, May 11 Last day of winter term classes Friday, May 18 Assignment 4 due ## Resources

Textbook
A list of the sections covered so far is here. 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.
See my page of links for web pages related to theoretical computer science. ## Course Handouts

To view a course handout, select one of the following links. Most of the documents are in PostScript format. (If you don't have a PostScript viewer, you can obtain one from here.) Updated May 2, 2001