【資料名稱】：Computational Complexity

【資料作者】：Sanjeev Arora and Boaz Barak

【資料日期】：2010

【資料語言】：英文

【資料格式】：PDF

【資料目錄和簡介】：

Computational complexity theory has developed rapidly in the past three decades. The
list of surprising and fundamental results proved since 1990 alone could fill a book: these
include new probabilistic definitions of classical complexity classes (IP=PSPACEand
thePCPTheorems) and their implications for the field of approximation algorithms; Shor’s
algorithm to factor integers using a quantum computer; an understanding of why current
approaches to the famousPversusNPwill not be successful; a theory of derandomization
and pseudorandomness based upon computational hardness; and beautiful constructions of
pseudorandom objects such as extractors and expanders.
This book aims to describe such recent achievements of complexity theory in the con-text of more classical results. It is intended to both serve as a textbook and as a reference
for self-study. This means it must simultaneously cater to many audiences, and it is care-fully designed with that goal. We assume essentially no computational background and
very minimal mathematical background, which we review in Appendix A. We have also
provided aweb sitefor this book at http://www.cs.princeton.edu/theory/complexity/
with related auxiliary material including detailed teaching plans for courses based on this
book, a draft of all the book’s chapters, and links to other online resources covering related
topics. Throughout the book we explain the context in which acertain notion is useful, and
whythings are defined in a certain way. We also illustrate key definitions with examples.
To keep the text flowing, we have tried to minimize bibliographic references, except when
results have acquired standard names in the literature, or when we felt that providing some
history on a particular result serves to illustrate its motivation or context. (Every chapter
has a notes section that contains a fuller, though still brief, treatment of the relevant works.)
When faced with a choice, we preferred to use simpler definitions and proofs over showing
the most general or most optimized result.