Computational_Complexity_A_Modern_Approach-Arora-Barak.pdf

(4146 KB) Pobierz
i
Computational Complexity: A
Modern Approach
Draft of a book: Dated August 2006
Comments welcome!
Sanjeev Arora and Boaz Barak
Princeton University
complexitybook@gmail.com
Not to be reproduced or distributed without the author’s
permission
Some chapters are more finished than others. References and attributions
are very preliminary and we apologize in advance for any omissions (but
hope you will nevertheless point them out to us).
DRAFT
ii
DRAFT
About this book
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 classi-
cal complexity classes (IP =
PSPACE
and the
PCP
Theorems) 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 famous
P
versus
NP
will not be successful; a theory of de-
randomization 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 the-
ory in the context of the classical results. It is intended to be a text and as
well as a reference for self-study. This means it must simultaneously cater
to many audiences, and it is carefully designed with that goal. Through-
out the book we explain the context in which a certain notion is useful,
and
why
things are defined in a certain way. Examples and solved exercises
accompany key definitions.
The book has three parts and an appendix.
Part I:
Basic complexity classes:
This part provides a broad introduc-
tion to the field and covers basically the same ground as Papadim-
itriou’s text from the early 1990s—but more quickly. It may be suit-
able for an undergraduate course that is an alternative to the more
traditional
Theory of Computation
course currently taught in most
computer science departments (and exemplified by Sipser’s excellent
book with the same name).
We assume essentially no computational background (though a slight
exposure to computing may help) and very little mathematical back-
ground apart from the ability to understand proofs and some elemen-
tary probability on finite sample spaces. A typical undergraduate
course on “Discrete Math” taught in many math and CS departments
DRAFT
Web draft 2006-09-28 18:09
iii
Complexity Theory: A Modern Approach. c 2006 Sanjeev Arora and Boaz Barak.
References and attributions are still incomplete.
iv
should suffice (together with our Appendix).
Part II:
Lowerbounds for concrete computational models:
This con-
cerns lowerbounds on resources required to solve algorithmic tasks on
concrete models such as circuits, decision trees, etc. Such models may
seem at first sight very different from the Turing machine used in Part
I, but looking deeper one finds interesting interconnections.
Part III:
Advanced topics:
This constitutes the latter half of the book
and is largely devoted to developments since the late 1980s. It includes
average case complexity, derandomization and pseudorandomness, the
PCP
theorem and hardness of approximation, proof complexity and
quantum computing.
Appendix:
Outlines mathematical ideas that may be useful for following
certain chapters, especially in Parts II and III.
Almost each chapter in Parts II and III can be read in isolation. This is
important because the book is aimed at many classes of readers.
•
Physicists, mathematicians, and other scientists.
This group has be-
come increasingly interested in computational complexity theory, es-
pecially because of high-profile results such as Shor’s algorithm and
the recent deterministic test for primality. This intellectually sophisti-
cated group will be able to quickly read through Part I. Progressing on
to Parts II and III, they can read individual chapters and find almost
everything they need to understand current research.
•
Computer scientists (e.g., algorithms designers) who do not work in
complexity theory per se.
They may use the book for self-study or
even to teach a graduate course or seminar. Such a course would
probably include many topics from Part I and then a sprinkling from
the rest of the book. We plan to include —on a separate website—
detailed course-plans they can follow (e.g., if they plan to teach an
advanced result such as the PCP Theorem, they may wish to prepare
the students by teaching other results first).
•
All those —professors or students— who do research in complexity
theory or plan to do so.
They may already know Part I and use the
book for Parts II and III, possibly in a seminar or reading course. The
coverage of advanced topics there is detailed enough to allow this. We
will provide sample teaching plans for such seminars.
We hope that this book conveys our excitement about this new field and
the insights it provides in a host of older disciplines.
DRAFT
Web draft 2006-09-28 18:09
Contents
About this book
Introduction
iii
1
I
Basic Complexity Classes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
11
12
14
14
18
19
22
23
24
25
27
27
33
34
36
37
39
41
42
45
46
51
1 The computational model —and why it doesn’t matter
1.1 Encodings and Languages: Some conventions
. . . . . . .
1.2 Modeling computation and efficiency
. . . . . . . . . . . .
1.2.1 The Turing Machine
. . . . . . . . . . . . . . . . .
1.2.2 The expressive power of Turing machines.
. . . . .
1.3 The Universal Turing Machine
. . . . . . . . . . . . . . .
1.4 Deterministic time and the class
P.
. . . . . . . . . . . . .
1.4.1 On the philosophical importance of
P
. . . . . . .
1.4.2 Criticisms of
P
and some efforts to address them
.
1.4.3 Edmonds’ quote
. . . . . . . . . . . . . . . . . . .
Chapter notes and history
. . . . . . . . . . . . . . . . . . . . .
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 NP
2.1
2.2
2.3
and NP completeness
The class
NP
. . . . . . . . . . . . . . . . . . . . . . . .
Non-deterministic Turing machines.
. . . . . . . . . . .
Reducibility and NP-completeness
. . . . . . . . . . . .
2.3.1 The Cook-Levin Theorem: Computation is Local
Expressiveness of boolean formulae
. . . . . . . .
Proof of Lemma 2.13
. . . . . . . . . . . . . . . .
2.3.2 More thoughts on the Cook-Levin theorem
. . .
2.3.3 The web of reductions
. . . . . . . . . . . . . . .
In praise of reductions
. . . . . . . . . . . . . . .
v
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
DRAFT
Web draft 2006-09-28 18:09
Complexity Theory: A Modern Approach. c 2006 Sanjeev Arora and Boaz Barak.
References and attributions are still incomplete.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin