Computational complexity
by Christos H. Papadimitriou · first published 1994
78% recommend22% neutral
Why HN recommends it
Thorough textbook on computational complexity, with good exercises and a strong bibliography. It serves as a reference for students and anyone studying complexity theory in depth.
Summarised by Claude from recommending comments
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
Mentions per year
What Hacker News says
Related books
2007–2019Elements of the Theory of Computation
Lewis, Harry R., and Christos H. Papadimitriou
Recommended by 5 · mentioned by 65 recommend · 6 mention5 recommend · 65 recommend
2008–2026Computers and intractability
Michael R. Garey, David S. Johnson
Recommended by 5 · mentioned by 115 recommend · 11 mention5 recommend · 115 recommend
2008–2026Introduction to the theory of computation
Michael Sipser
Recommended by 66 · mentioned by 8966 recommend · 89 mention66 recommend · 8966 recommend
2008–2025Introduction to automata theory, languages, and computation
John E. Hopcroft, Jeffrey D. Ullman, Rajeev Motwani
Recommended by 24 · mentioned by 3324 recommend · 33 mention24 recommend · 3324 recommend
2008–2024Theory of computation
Michael Sipser
Recommended by 14 · mentioned by 1914 recommend · 19 mention14 recommend · 1914 recommend
2007–2026Quantum Computing Since Democritus
Scott Aaronson
Recommended by 73 · mentioned by 9273 recommend · 92 mention73 recommend · 9273 recommend
2007–2026Compilers, principles, techniques, and tools
Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
Recommended by 195 · mentioned by 659195 recommend · 659 mention195 recommend · 659195 recommend
2008–2026Types and Programming Languages
Benjamin C. Pierce
Recommended by 132 · mentioned by 226132 recommend · 226 mention132 recommend · 226132 recommend
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)
on “Finding the top K items in a list efficiently” ↗I would suggest "Computational Complexity" by C.H. Papadimitriou Great material, great exercises, very good bibliography
on “Ask HN: Good books on computational complexity?” ↗Yes. I also like Papadimitriou's textbooks: Elements of the Theory of Computation and Computational Complexity.
on “Technical Papers Every Programmer Should Read (At Least Twice)” ↗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.
on “A Course on Automata Theory” ↗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
on “Recommended Books on Computational Complexity Theory” ↗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.…
on “I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA” ↗…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.
on “Problems harder than NP-Complete” ↗…example), but of course, there are always the textbooks designed specifically for that field. For instance, Dummit and Foote's Abstract Algebra, Baker's Comprehensive Course in Number Theory, Papadimitriou's Computational Complexity, and so on. Those are pretty easy to find with Google, though, if you search for influential textbooks in those fields. This list is hopelessly incomplete, but I think it is quite a good broad survey…
on “Mathematical Cryptology [pdf]” ↗Ah I see. Well in any case, thanks for the link, it led to several books I'm interested to check out... - Computers and Intractability: A Guide to the Theory of Np-Completeness - Computational Complexity (your page has the one by Papadimitriou, but putting it on my Goodreads list led to two others of the same name by Goldreich and Arora/Barak I didn't know of)
on “Ask HN: What are the most fundamental books on computer science?” ↗