11
$\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$
1
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$
2
  • $\begingroup$ I've heard Sipser is good for the core topics as taught in a typical intro algorithms class, and Arora-Barak is better for more advanced topics. $\endgroup$
    – Neal Young
    Oct 21 at 1:42
  • $\begingroup$ garey and johnson summarizes 50 years of theory. i finished the book. +daniel 2380 $\endgroup$ Oct 28 at 13:09
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.

$\endgroup$
2
$\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.

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

See Elements of Computation Theory by Arindama Singh.

$\endgroup$
3
  • 1
    $\begingroup$ Is it possible to provide some more information about this book and why you recommend it? Thank you! $\endgroup$ Jun 26 '18 at 5:02
  • 3
    $\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$ Jul 3 '18 at 1:16
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.

$\endgroup$
0
$\begingroup$

For Automata Theory, get the 1979 edition of "Automata Theory, Languages and Computation". Unlike the 3rd edition, it is not an introductory book, but goes into lots of detail about all the specifics of automata theory. It covers things like trios, cones, abstract families of languages, etc. that most undergrad books skip.

$\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.