Commentary by cpressey on Computational Complexity works
Computers and Tractability
The classic work presenting a compilation of many NP-complete problems.
Computational Complexity (Papadimitriou)
Really quite good book on the subject. One memory I have from it is the economical definition of Turing machines; they're defined as a 4-tuple (in contrast to other author's definitions using, say, a 7-tuple); another is the discussion early on of what metrics can be used for complexity and what can't, and how one can define pathological metrics.
Computational Complexity (Wagner and Wechsung)
Gosh, this is incredibly heavy. It's hard to imagine any individual ever owning this book; I can only imagine it belonging to a university library. That sort of book.
Why Philosophers Should Care About Computational Complexity
There's some good stuff here, but it's not all good stuff.
Mainly, this is where I discovered Cobham's P-complete formulation. It comes via another paper via another paper though, so it should really be described there.
There are a few other interesting things in this essay though. The "waterfall as computation" example, for example.
Protein folding is NP-hard
Complexity Hierarchies Beyond Elementary
I need to skim this and take some notes.
The Typed Lambda Calculus is not Elementary Recursive
Computability and Complexity (Stanford Encyclopedia of Philosophy)
Descriptive Complexity
Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science
Articles are CC-BY-something licensed.