Can anyone recommend a good book on the subjects of computability and computational complexity? What are the de facto standard texts (say, for graduate students) in this area?
I've heard a thing or two on these subjects from "CS people" back at the university. With lots of hand-waving they talked about the halting problem, about P versus NP, and so on.
What I would like to find now is an actual mathematics textbook (as opposed to programming and/or popular textbooks). With rigorous definitions and proofs. I'm no stranger to mathematical logic, including things like partial recursive functions and Godel's theorem. I suspect I would benefit from reading a standard graduate-level text on computational complexity. All I need now is some references to such texts. Any suggestions?
You should take a look at Computational Complexity: A Modern Approach by Arora and Barak if you haven't already. I have also heard good things about Goldreich's Computational Complexity: A Conceptual Perspective but I haven't read it.