Customer Reviews

The Complexity Theory Companion

5 star:		(0)
4 star:		(0)
3 star:		(1)
2 star:		(0)
1 star:		(0)

 

 

The aim of this book is to introduce complexity theory using a more technique-oriented approach, which is not seen in other complexity theory textbooks. Techniques covered are:
- self-reducibility
- one-way function
- tournament divide and conquer
- isolation technique (aka. isolation lemma)
- witness reduction
- polynomial interpolation
- nonsolvable group (used in Barrington's theorem to show that width-five branching program can simulate any Boolean formula and thus the complexity class NC1)
- random restriction technique
- polynomial technique
This seems like an awesome approach and I couldn't agree with the authors more about the organization. In fact, this was the reason why I bought the book.

Unfortunately, the results are badly presented in a lot of places. Proofs are extremely tedious with unnecessary details and notations. This overly formal approach prevents the reader from seeing the big strategy or idea behind each proof. For example, Barrington's theorem has a very elegant and readable 1-page proof (cf. Boppana-Sipser survey "The Complexity of Finite Functions", 1989). But I couldn't understand why they decided to include an ugly 6-page proof in this book!

The students will learn more from "Computational Complexity" by Arora and Barak, where only the most elegant and readable versions of proofs are selected. Papadimitriou does not cover recent results, but is also a solid textbook with full of excellent exercises.