Computational complexity for physicists
Stephan Mertens · Computing in Science & Engineering · 2002
The theory of computational complexity has some interesting links to physics, in particular to quantum computing and statistical mechanics. The article contains an informal introduction to this theory and its links to physics.