9
$\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
  • $\begingroup$ @Sadeq True, though this one is asking specifically about textbooks, presumably at the level of Sipser $\endgroup$ – Huck Bennett Dec 4 '10 at 8:10
  • 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$ @Robin: I think ranking books and papers is OK, it is different from ranking people or departments, but I think it might be better to continue this discussion on meta. $\endgroup$ – Kaveh Dec 5 '10 at 7:02
12
$\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$
8
$\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.

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

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

| cite | improve this answer | |
$\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
0
$\begingroup$

I recommend "Computability and Logic" by George S. Boolos and John P. Burgess. It's formal, rigorous and fairly thorough. It's a book on computability only, not covering computational complexity.

Notice that some other answers suggested books that focus on computational complexity instead of computability. For instance, (i) "Computational Complexity: A Modern Approach" by Arora and Barak; (ii) "Computational Complexity" by Christos H. Papadimitriou; and (iii) "Computational Complexity: A Conceptual Perspective" by Oded Goldreich.

$\endgroup$
0
$\begingroup$

I recommend Math and Computation by Avi Wigderson if you're mainly interested in complexity theory. This is probably best supplemented by other books mentioned in this thread, as it's less rigorous. However the writing is excellent, and would be my go-to for a quick reference or enjoyable read.

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

It is very hard to define what best means! Anyway, The nature of computation by Cris Moore and Stephen Mertens is very good. The book is nice to either get an introduction to the big ideas of the theory of computation if one is not interested too much in mastering the techniques, or to lift one's head of the track after learning many technicalities. It serves to my mind a quite different purpose than Arora & Barack's book for instance.

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

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.