6 ms·

Recommended Books on Computational Complexity Theory

19 points by hacker-l 2y ago

I am interested in computational complexity theory, especially in the discussion of the P vs NP problem and complexity classes. Could you recommend some books that provide an in-depth introduction to these topics?

mayd 2y ago
John E. Hopcroft, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation.
zfnmxt 2y ago
I personally used Sipser, but I think the book by Neil Jones [1] that takes a programming languages approach is really cool, and potentially more along the average HN reader's interests. [1] http://hjemmesider.diku.dk/~neil/comp2book2007/book-whole.pdf http://hjemmesider.diku.dk/~neil/comp2book2007/book-whole.pd...
dysoco 2y ago
I believe I used Introduction to the Theory of Computation by Sipser for this and it's probably the one textbook most universities are going to use. Maybe for more in depth reference about the algorithms at play Introduction to Algorithms (Cormen) will complement nicely; I don't remember how much Sipser goes into describing the algos.
sky2224 2y ago
As someone else said already: Theory of Computation by Sipser is the go to intro book for this. I'd recommend really reading the book front to back honestly. It helps to have a complete picture of everything that leads up to getting into complexity theory. Sipser also has corresponding lectures that are available for free on YouTube here: https://www.youtube.com/watch?v=9syvZr-9xwk&list=PLidiQIHRzpXIFFbyGrWkqXXVj0BztDcTF https://www.youtube.com/watch?v=9syvZr-9xwk&list=PLidiQIHRzp....
- a_tartaruga 2y ago
  Sipser is one of the best textbooks of all time from any field
- sn9 2y ago
  You can also find solutions manuals in the usual places.
bcherny 2y ago
Scott Aaronson’s Quantum Computing Since Democritus is a clear, entertaining explanation of computational complexity theory as applied to both classical and quantum computers. I thoroughly enjoyed the book, and have recommended it to a number of friends. https://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565 https://www.amazon.com/Quantum-Computing-since-Democritus-Aa...
trod123 2y ago
The Dragon Book for Compilers
- dloranc 2y ago
  But it's more about compilers and their design than typical ideas about computational complexity.
dloranc 2y ago
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
wannabebarista 2y ago
Here's some more specific recommendations from the books people have mentioned: * Part 3 of Sipser’s Introduction to the Theory of Computation * The first half of Arora and Barak's Computational Complexity No one had mentioned this one yet, but it provides nice exposition: Goldreich’s Computational Complexity: a Conceptual Perspective. Here are some notes I put together on what's out there for learning complexity theory and a bit on where you can go next: https://bcmullins.github.io/complexity_theory_resources/ https://bcmullins.github.io/complexity_theory_resources/.
shaneevan21 2y ago
[dead]

19 points by hacker-l 2y ago

mayd 2y ago

John E. Hopcroft, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation.

zfnmxt 2y ago

I personally used Sipser, but I think the book by Neil Jones [1] that takes a programming languages approach is really cool, and potentially more along the average HN reader's interests. [1] http://hjemmesider.diku.dk/~neil/comp2book2007/book-whole.pdf http://hjemmesider.diku.dk/~neil/comp2book2007/book-whole.pd...

dysoco 2y ago

I believe I used Introduction to the Theory of Computation by Sipser for this and it's probably the one textbook most universities are going to use. Maybe for more in depth reference about the algorithms at play Introduction to Algorithms (Cormen) will complement nicely; I don't remember how much Sipser goes into describing the algos.

sky2224 2y ago

As someone else said already: Theory of Computation by Sipser is the go to intro book for this. I'd recommend really reading the book front to back honestly. It helps to have a complete picture of everything that leads up to getting into complexity theory. Sipser also has corresponding lectures that are available for free on YouTube here: https://www.youtube.com/watch?v=9syvZr-9xwk&list=PLidiQIHRzpXIFFbyGrWkqXXVj0BztDcTF https://www.youtube.com/watch?v=9syvZr-9xwk&list=PLidiQIHRzp....

a_tartaruga 2y ago
Sipser is one of the best textbooks of all time from any field
sn9 2y ago
You can also find solutions manuals in the usual places.

bcherny 2y ago

Scott Aaronson’s Quantum Computing Since Democritus is a clear, entertaining explanation of computational complexity theory as applied to both classical and quantum computers. I thoroughly enjoyed the book, and have recommended it to a number of friends. https://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565 https://www.amazon.com/Quantum-Computing-since-Democritus-Aa...

trod123 2y ago

The Dragon Book for Compilers

dloranc 2y ago
But it's more about compilers and their design than typical ideas about computational complexity.

dloranc 2y ago

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

wannabebarista 2y ago

Here's some more specific recommendations from the books people have mentioned: * Part 3 of Sipser’s Introduction to the Theory of Computation * The first half of Arora and Barak's Computational Complexity No one had mentioned this one yet, but it provides nice exposition: Goldreich’s Computational Complexity: a Conceptual Perspective. Here are some notes I put together on what's out there for learning complexity theory and a bit on where you can go next: https://bcmullins.github.io/complexity_theory_resources/ https://bcmullins.github.io/complexity_theory_resources/.

shaneevan21 2y ago

[dead]