Computational complexity

What Hacker News says

1. dlorancJun 2024
   Books I have and recommend:

   Introduction to the theory of computation - Michael Sipser

   Computational complexity - Arora, Barak

   Computational Complexity - Christos H. Papadimitriou

   Computers and intractability - Michael R. Garey, David S. Johnson

   Show morethread
2. steepsMay 2023
   "Quantum Computing Since Democritus" mentioned in the other answer is definitely good fun, but I find it a bit tricky in places and it very much has a quantum skew. If you're after a textbook reference, then I really like Papadimitriou's Computational Complexity (no longer in print, but used copies/library copies are about) or Arora and Barak's Computational Complexity for something a bit more modern with a nice coverage.
   Show morethread
3. ScottAaronsonJun 2018
   A classic from 1994 is "Computational Complexity" by Papadimitriou.

   Two good sources for newer material (from the past quarter-century) are "Complexity Theory: A Modern Approach" by Arora and Barak, and "The Nature of Computation" by Mertens and Moore.

   A personal, idiosyncratic favorite is "Gems of Theoretical Computer Science" by Uwe Schoning.

   thread
4. grumpy-buffaloAug 2015
   If you're interested in computational complexity theory, I recommend "Computational Complexity" by Christos Papadimitriou. It's a classic, though it's a bit dated.
   thread
5. nandemoDec 2011
   Yes.

   I also like Papadimitriou's textbooks: Elements of the Theory of Computation and Computational Complexity.

   thread
6. veyronJun 2011
   I'd recommend you start from Sipser [http://www.amazon.com/Introduction-Theory-Computation-Michae...] or Papadimitriou [http://www.amazon.com/Computational-Complexity-Christos-H-Pa...] to learn more about complexity theory (then we can discuss why your response is nonsense)
   thread