3 ms·
Could you perhaps recommend some book on computational complexities? My CS curriculum back then mostly included the usual Chomsky hierarchy, but was quite lean
by kaba0 4y ago
Could you perhaps recommend some book on computational complexities? My CS curriculum back then mostly included the usual Chomsky hierarchy, but was quite lean on anything other than P/NP, and most books I found were also mostly about the “basics”.
- flancian 4y agoNot the parent but I really enjoyed Scott Aaronson's "Quantum Computing Since Democritus": https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democritus https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democr... Based on: https://www.scottaaronson.com/democritus/ https://www.scottaaronson.com/democritus/
- steeps 4y ago"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.