I recently attended a lecture on an introduction to computation complexity and I am looking to find out more, I haven't studied computer science or discrete mathmateics at university and I was wondering if anyone could recommend any relatively simple books or reading material that could help me understand the topic more


closed as primarily opinion-based by D.W., FrankW, David Richerby, Rick Decker, Nicholas Mancuso Jun 27 '14 at 20:37

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Look at the books recommended in the syllabuses of undergrad complexity theory courses. That's as "relatively simple" as it gets and it'll give you an idea of what books the people in the field think are the best. $\endgroup$ – David Richerby Jun 27 '14 at 7:49
  • $\begingroup$ cs.se popular cs textbooks list $\endgroup$ – vzn Jun 27 '14 at 16:38

Classic texts on computational complexity include Hopcroft & Ullman's text {1} and Sipser's text {2}. With patience, they should both be accessible.

{1} Hopcroft, John E., R. Motwani, and J. D. Ullman. "Introduction to Automata Thoery, Language, and Computation (2nd edition)". Addison-Wesley, Reading (2001).

{2} Sipser, Michael. Introduction to the Theory of Computation. Cengage Learning, 2012.


You may also be interested in scanning answers to the following questions on the TCS site:




They contain further pointers, and many comments.

But the two books suggested by Ari Trachtenberg are certainly a good start.


Not the answer you're looking for? Browse other questions tagged or ask your own question.