8
$\begingroup$

I look for a good text to learn basics of computational complexity.

I've read some parts of the first two chapters of "Computational Complexity: A Modern Approach" by Boaz Barak and Sanjeev Arora, it's readable and gives the big picture but I find it not to be rigorious enough for me. I'm a mathematics student so I want a more rigorous treatment of the subject. So, the text I look for should:-

1- Define Turing machines formally and prove the basic results in a formal way not using handy-waving arguments. For example, Boaz treatment of Turing machines is not rigorous and so I'd love to see more precise treatment of that.

2- Give proofs that are rigorous enough like those I read in mathematics texts and are not just "overviews".

What are your recommendations? What is the texts that satisfies my needs as close as possible?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Following are my recommendations:

  1. Introduction to Theory of Computation by Michael Sipser. It is an introductory book. Although proofs are complete and not hand waving, but not much maths is needed as a pre requisite. Although Turing machines are covered nicely.
  2. Complexity and cryptography by Talbolt and Welsh. In this book little math background is required. Turing machines is not covered in much details. But the book gives proofs for almost all theorem's it introduces.

    From my experience ( as I am a beginner myself ) Sanjeev Arora and Boaz Barak is the most concise with covering advanced topics like quantum computation etc. Although I think you should have a back ground in probability, number theory to read the part I of the book intended to be for undergraduates, as the book leaves some proofs upto the readers. Again for number theory the book I find readable as ( as there is no pre requisite ) : Number theory by Willian Stein.
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ My limited experiences with Sipser have left me quite unsatisfied and with little desire to come back. I don't think it's what the OP is looking for, but may be worth checking out. $\endgroup$
    – Raphael ♦
    Apr 15, 2016 at 13:15
2
$\begingroup$

The topics you have mentioned mostly belong to Theory of Automata. I think the book Introduction to Automata Theory, Languages, and Computation (2nd edition) by Hopcroft and Ullman is what you want.

The book by Arora and Boaz, thought not mentioned, does assume you are well conversed with theory of automata. They however need more rigorous time and space bounds for Turing machines in their book, for which they have given quite extensive proofs.

So Arora and Boaz is a good book for Computational Complexity but not a great book if you are interested only in Theory of Automata or NP completeness (both are dealt with and finished in one or two chapters, till chapter 4, if I remember correctly).

Honestly, I am surprised that you think that Arora and Boaz's book is not rigorous. Their style, as I understand, is to give proofs for difficult theorems, but leave proofs for simpler theorems by giving sufficient hints and/or by giving proofs for specific cases. This saves the book from having excessive symbols, subscripts, and superscripts bloat that many other text books and almost all scientific papers suffer.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I have heard that the latest edition(s) of HWU does no longer expose the depth and rigor the older ones did. $\endgroup$
    – Raphael ♦
    Apr 15, 2016 at 13:13
  • $\begingroup$ You are probably correct. I have heard the same from quite a few people. I have changed it to second edition. But in my opinion only the exercises are diluted, text matter is mostly same, except they have put English in place of many mathematical symbols. $\endgroup$
    – Sarvottamananda
    Apr 15, 2016 at 13:43
  • $\begingroup$ @Raphael The 2nd ed was intended for graduate students of 1970s, while more modern editions aim undergrads. $\endgroup$
    – Anton Trunov
    Apr 16, 2016 at 6:15
  • $\begingroup$ @AntonTrunov Huh. I found the 1970s version quite good for undergrad education (Germany STEM-focused university). Go figure. $\endgroup$
    – Raphael ♦
    Apr 16, 2016 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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