CSI5140 H -- Computational Complexity -- Fall 2010


[Announcements] [Lectures] [Syllabus] [Paper List] [Links]


General Information

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

Office Hours: Thursday 3:00-4:00PM, in my office (SITE 5072)

Lectures: Thursday 4:00-7:00PM ; Brooks Residence (BRS) 204

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: