I’m trying to learn a bit (or maybe more than just a bit) about computational complexity. I could download a few books which looked interesting to me:

* Agrawal & Arvind (Perspectives) 2014

* Arora & Barak (A modern approach) 2009 (I’ve read half of this book so far, and found it really very good)

* Du & Ko (Theory of Computational Complexity, Second Edition) 2014

* Goldreich (PNP) 2010

* Goldreich (A conceptual approach) 2008

* Meyers (Encyclopedia, 3000+ pages) 2012

* Parberry (Algo Analysis 4th edition) 2001

* Trevisan (Lecture notes) 2011: concise and easy to read

* Watanabe (Colmogorov complexity) 1992

* Zimand (Quantitative Perspective) 2004

(This field is developing so fast that older books published before 1990 are considered obsolete and so they are not included in the list)

Any comments, suggestions for new items welcome :-)

Nhân dịp năm mới Bính Thân, em kính chúc GS và phu nhân cùng công tử và tiểu thư và đôi bên gia quyến thật nhiều sức khỏe, an khang, hạnh phúc, tài lộc, thành công; kính chúc hai vị ra sức dịch sách, viết sách, xuất bản sách phục vụ nhân dân !

Cảm ơn bạn, và chúc bạn năm mới hạnh phúc

How about this book

http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&r=1&review_format=html&s4=Pudlak&s5=Logical%20Foundations%20of%20Mathematics%20and%20Computational%20Complexity&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq

MR3076860 Reviewed

Pudlák, Pavel(CZ-AOS-NDM)

Logical foundations of mathematics and computational complexity.

A gentle introduction. Springer Monographs in Mathematics. Springer, Cham, 2013. xiv+693 pp. ISBN: 978-3-319-00118-0; 978-3-319-00119-7

03-02 (03D15 03E35 03F20 68-02 68Q15 68Q19 68Q87)

PDF Clipboard Series Book Make Link

Pavel Pudlák’s new book is a most unusual enterprise: in non-technical, yet by no means imprecise, terms it introduces the reader to the cosmos of mathematical logic, seen in particular through the lens of complexity. The subtitle of the book is `A gentle introduction’, and this describes the approach very well. I do not know of a similar endeavour. Saying that this book fills a gap is an understatement; it is a new kind of mathematical textbook of which we ought to have many more.

The outline of the book is as follows. Chapter 1 is an introduction to mathematical structures, sets and the axiomatic method, and Chapter 2 explores the foundations of logic and mathematics by covering foundational concepts from logic (e.g. syntax, models, Gödel’s completeness and incompleteness theorems) and computability (e.g. Turing machines, Church-Turing Thesis). The book then delves deeper into important subject areas of mathematical logic: set theory in Chapter 3, incompleteness and independence in Chapter 4, computational complexity in Chapter 5, and proof complexity in Chapter 6. The volume ends in Chapter 7 with a discussion of fundamental connections between logic, foundations of mathematics, and philosophy. The book comes with many pointers to further reading and contains several indexes, which makes it easy to use for reference purposes.

At first superficial glance, one might wonder for whom this book was written: might it not be too complicated for the layman and too elementary for the logician? However, at closer inspection I believe neither worry to be justified; this book will have a large audience. For the non-expert it offers indeed a `gentle introduction’ to logic that is well selected and excellently explained. And for the logician it certainly offers some of the best introductions to those topics outside their area of direct expertise. What is more, it contains plenty of informal explanations, intuition and motivation. While there are many textbooks that offer full technical details, in many of its passages this book lets you see behind the scene. It is the kind of explanation and discussion that I have been longing for since I was a student.

It is truly a gift to the logic and wider communities that one of the great masters of the field undertook the laborious effort of many years to share his insights with a larger audience. This book is very enjoyable to read and I wish it all success.

Quyển đó có vẻ hơi thiên về logic và nhẹ về phần thuật toán chị Vân ạ