### CSI5140 A -- Computational Complexity --
Winter 2014

####

####

### General Information

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

**Office Hours**: Tuesday 13:00-14:00PM, in my office (SITE 5072)

**Lectures**: Tuesday / Thursday)
16:00-17:30 / 14:30-16:00; TBT 319 / SMD 227

### Overview

**Topics**: Basic
computation models. 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. Inside P and Beyond NP. Randomized
computation.

**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)