6
$\begingroup$

In University we used the Sipser text and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression. I borrowed that book and don't have one in my collection, so I need one. So to the question, are there are any other books which could be seen as better and possibly more complete?

I didn't see a community wiki section here, so I couldn't note it as such.

$\endgroup$
  • 5
    $\begingroup$ possible duplicate of What Books Should Everyone Read? $\endgroup$ – M.S. Dousti Dec 4 '10 at 8:05
  • 6
    $\begingroup$ @Huck: Doesn't the Computational Complexity entry already answer this? If not, how about Books on automata theory for self-study? (Both were present in the link I offered as possible duplicate.) $\endgroup$ – M.S. Dousti Dec 4 '10 at 9:07
  • 2
    $\begingroup$ I don't prefer this question. I'm not sure a question (implicitly) asking people to vote on a best textbook is focused, clear or objective... $\endgroup$ – Daniel Apon Dec 4 '10 at 15:15
  • 1
    $\begingroup$ This was flagged for closing, but based on the discussion I'm going to hold off for now, since there appears to be a sense that this could be useful independently of the other question. $\endgroup$ – Suresh Venkat Dec 4 '10 at 18:54
  • 4
    $\begingroup$ why all the downvotes ? it's not consistent to downvote this when there are other questions of the same type. $\endgroup$ – Suresh Venkat Dec 4 '10 at 23:32
11
$\begingroup$

I strongly recommend the book Computational Complexity: A Modern Approach by Arora and Barak. When I took computational complexity at my Master level, the main textbook is Computational Complexity by Papadimitriou. But, maybe due to my background in Software Engineering, I found the writing in Papadimitriou challenging at times. Whenever I had problem understanding Papadimitriou's book, I simply went back to Sipser, or read the draft of Arora and Barak.

In retrospect, I really like Papadimitriou's book, and I often find myself looking up from this book. His book has plenty of exercises that are quite effective at connecting readers to research-level questions and open problems.

In any case, you should have a look at both Papadimitriou and Arora-Barak. People also suggest Oded Goldreich's textbook, but I really prefer the organization of Arora-Barak.

$\endgroup$
7
$\begingroup$

In my personal opinion, the Sipser book is still great. It's by far the most readable book on the subject.

The Sipser book also is an introduction, so coming back to it after some time isn't too trying on your memory.

That said, Papadimitrou's book is a good book for getting around the more advanced topics.

$\endgroup$
1
$\begingroup$

See Elements of Computation Theory by Arindama Singh, pub: Springer.

$\endgroup$
  • $\begingroup$ Is it possible to provide some more information about this book and why you recommend it? Thank you! $\endgroup$ – Michael Wehar Jun 26 '18 at 5:02
  • 1
    $\begingroup$ For any topic, it starts with the requirements informally, and then goes for a formalization very methodically. It includes lots of examples, exercises, and problems. Its notation is very intuitive. It does not sacrifices rigor. It discusses almost all of ToC results which are considered fundamental. $\endgroup$ – Sunita Jul 2 '18 at 6:04
  • $\begingroup$ Thank you very much for providing more info!! :) $\endgroup$ – Michael Wehar Jul 3 '18 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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