Computational Complexity for Physicists

Abstract

These lecture notes are an informal introduction to the theory of computational complexity and its links to quantum computing and statistical mechanics.

references updated, reprint available from http://itp.nat.uni-magdeburg.de/~mertens/papers/complexity.shtml