3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot @Carl! I've seen references to the book by Arora and Barak somewhere on the net. Now that you've given a "second opinion" - I'll definitely give it a read. $\endgroup$ – Dan Shved May 25 '13 at 13:26
  • $\begingroup$ @DanShved: Glad to be of help. $\endgroup$ – 77474 May 25 '13 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.