Course outline:
Computability: languages and automata, equivalence of different models
of computation, Turing machines and problems that are not computable.
Complexity classes defined in terms of time, space, and circuits.
Reduction and completeness. Proof systmes. Randomized algorithms and
cryptography.
Textbook:
Michael Soltys. An introduction to computational complexity
[Click here for a
sample]
2009
Published by the
Jagiellonian University Press.
Nov 4: Assignment 3, due on November 23, has been posted below.
Oct 11: Assignment 2, due on November 2, has been posted below.
Sept 29: Here are the
slides from yesterday's
lecture: context-free grammars.
Sept 27: In tomorrow's lecture we are going to talk a little
bit about assignment 1. Please bring your questions. The assignment
deadline is extended to October 11 (just place it in the instructor's
mailbox), as there is going to be no lecture on October 5 (the
instructor is away at a conference). Will make up for the lost
lecture at the end, or during the term; we'll see.