If you are learning about complexity theory for the first time, I recommend you read Papadimitriou's excellent book on the subject. One aspect about this book that I did not like is it's lack of combinatorial analysis, and its more generic, structural apporoach (i.e. focusing on robust sets of problems). Some may prefer this, but I think the combinatorial approach is more in line with mainstream computer science.

Скачать книгу бесплатно (pdf, 10.19 Mb)

---

Читать «Structural Complexity I (Texts in Theoretical Computer Science. An EATCS Series)»