### CSI5140 A -- Computational Complexity --
Fall 2008

####

####

### General
Information

**Professor**: *Iluju Kiringa* (*kiringa@site.uottawa.ca*)

**Office Hours**: Wednesdays 11:30-12:30AM
(Increased on rush days) in my office (SITE 5072)

**Lectures**: Wednesday 1:00-4:00PM ; CBY E016

### Overview

**Topics**: Basic computation modelss.
Undecidability and related proof techniques. Basic computational resources and their associated
complexity classes (P, NP, Co-NP, PSPACE, ...). Relationships among resources and
complexity classes. Theory of class completeness (NP completeness, PSPACE completeness, ...) and
related proof techniques. Randomized computation. Inside P and Beyond NP.

**Prerequisites**: Required is a solid knowledge of
design and analysis of algorithms as well as undergraduate notions of
computability.

**Text book**: M.J. Sipser,
*Introduction to the Theory of Computation*, 2nd Edition, Thompson, 2006.

**Supplemental reading**:

- C. Papadimitriou,
*Computational Complexity*, Addison Wesley, 1994
(This is a more advanced book than Sipser's book; it covers much of the material needed for
the course and has been for a long time the classic textbook in the area)
- M. R. Garey and D. S. Johnson,
* Computers and Intractability: A Guide to the Theory
of NP-completeness*, Freeman, 1979 (This is the classic book on NP-completeness)
- D. Z. Du and K. Ko,
*Theory of Computational Complexity*, Wiley, 2000 (A very
advanced book, very useful reference for experts in the area)
- J.E. Hopcroft and J.D. Ullman,
*Introduction to Automata Theory, Languages,
and Computation*, 2nd Edition, Addison Wesley, 2001 (The last 3 chapters are another source on
NP completeness material)