This is a textbook on computational complexity theory. It is intended as a text for an advanced undergraduate course or introductory graduate course, or as a reference for researchers and students in computer science and allied fields such as mathematics and physics.
This page contains a draft of the book and links to additional relevant material and teaching plans for courses based on this book.
Update: We have submitted the book to Cambridge University Press on June 2008, the expected publication date is March 2009. We no longer accept comments on the draft, though we would be grateful for comments on the published version, once it is ready.
May the force of P and NP be with you