3
$\begingroup$

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

$\endgroup$
  • $\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
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read

and

https://cstheory.stackexchange.com/questions/3540/what-are-the-recent-tcs-books-whose-drafts-are-available-online

They contain further pointers, and many comments.

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

| cite | improve this answer | |
$\endgroup$

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