Computability and complexity

What Hacker News says

1. drdreyJan 2018
   Computability and Complexity by Neil Jones: http://www.diku.dk/~neil/comp2book2007/book-whole.pdf

   It is extremely readable and presents very theoretical concepts in a pragmatic way. Love it.

   thread
2. dmmckayJul 2015
   Lipton wrote a pretty decent and short intro to QC that builds the theory a little differently from usual. It is aimed more towards Mathematicians and Computer Scientists than Physicists, I believe, but I think it is pretty understandable in general.

   I think Sipser is probably the best introduction to Computation if you do not have a background in Computability and Complexity. Arora and Barak's text has a much larger breadth and is much more detailed as far as Complexity goes. It is the more appropriate of the two if you are just interested in Computational Complexity.

   Show morethread