Computability and Complexity

Computability and Complexity - Overview

  1. Introduction to Computability and Complexity
  2. Existence of unsolvable problems
  3. The Halting Problem
  4. Computational Complexity Theory
  5. NP and NP-completeness
  6. Cook's Theorem

All of the above

Postscript version of OHP slides (complete) (8 to page)

Postscript Version of Proof of Cook's Theorem (8 to page OHP)

See also:

Algorithm Design Paradigms

PED Home Page