Computational Complexity: A Conceptual Perspective
[drafts of a book by Oded Goldreich]
See copyright notice.
Below is the book's tentative preface
and Organization.
The following versions are available on-line.
-
A preliminary draft (dated January 2006): in
gzip .ps
format and in six parts corresponding to chapters
0-2,
3-5,
6-7,
8-9,
10-B,
C--.
See also related material
and errata.
-
Partial revisions (in PDF):
Chap.
7-9 and Apdx C (June 2006),
Chap.
6 & 10 and Apdx D (July 2006),
Sec 1.2
and Chap. 2 (Sept. 2006),
Chap. 3-5
and Apdx E (Oct. 2006),
Preface
and Sec. 1.1 (Oct. 2006),
Preface,
Chap. 1 & 10, and Ref. (Dec. 2006).
-
Corresponding PDF files can be found
HERE.
A full revision (dated December 2006): in a single file
gzip .ps
format.
-
Latest avaiblabe revisions (in PDF):
Chap 0-2
(Dec. 2006),
Chap 3-5
(Jan. 2007),
Chap 6-7
(Feb. 2007),
Chap 7-8
(Mar. 2007),
Chap 9-10
(Apr. 2007),
Apdx+Refs
(May 2007).
See also related material.
Last updated: May 2007.
Preface (tentative, Jan. 2006)
The strive for efficiency is ancient and universal,
as time and other resources are always in shortage.
Thus, the question of which tasks can be performed efficiently
is central to the human experience.
A key step towards the systematic study of the aforementioned question
is a rigorous definition of the notion of a task and of procedures for
solving tasks. These definitions were provided by computability theory,
which emerged in the 1930's. This theory focuses on computational tasks,
and considers automated procedures
(i.e., computing devices and algorithms)
that may solve such tasks.
In focusing attention on computational tasks and algorithms,
computability theory has set the stage for the study of the
computational resources (like time) that are required by such algorithms.
When this study focuses on the resources that are necessary for
any algorithm that solves a particular task (or class of tasks),
the study becomes part of the theory of Computational Complexity
(also known as Complexity Theory).
Complexity Theory is a central field of the theoretical foundations
of Computer Science. It is concerned with the study of
the intrinsic complexity of computational tasks.
That is, a typical Complexity theoretic study looks at a task
(or a class of tasks) and at the computational resources
required to solve this task,
rather than at a specific algorithm or algorithmic scheme.
Actually, research in Complexity Theory tends to
start with the computational resources themselves,
and addresses the effect of limiting these resources
on the class of tasks that can be solved.
Thus, Computational Complexity is the study of the
what can be achieved within limited time
(and/or other limited natural computational resources).
The (half-century) history of Complexity Theory has witnessed
two main research efforts (or directions).
The first direction is aimed towards actually establishing concrete
lower bounds on the complexity of problems,
via an analysis of the evolution of the process of computation.
Thus, in a sense, the heart of this direction is a ``low-level''
analysis of computation. Most research in circuit complexity
and in proof complexity falls within this category.
In contrast, a second research effort is aimed at exploring
the connections among computational problems and notions,
without being able to provide absolute statements regarding
the individual problems or notions.
This effort may be viewed as a ``high-level'' study of computation.
The theory of NP-completeness as well as
the studies of approximation, probabilistic proof systems,
pseudorandomness and cryptography
all fall within this category.
The current book focuses on the latter effort (or direction).
We list several reasons for our decision to focus
on the ``high-level'' direction.
The first is the great conceptual significance
of the known results; that is, many known results
(as well as open problems)
in this direction have an appealing conceptual message,
which can also be appreciated by non-experts.
Furthermore, these conceptual aspects may be explained
without entering into excessive technical detail.
Consequently, the ``high-level'' direction is more suitable
for an exposition in a book of the current nature.
Finally, there is a subjective reason:
the ``high-level'' direction is within our own expertise,
while this cannot be said about the ``low-level'' direction.
The last paragraph brings us to a discussion
of the nature of the current book,
which is captured by the subtitle (i.e., ``a conceptual perspective'').
Our thesis is that complexity theory is extremely rich in conceptual
content, but this content is rarely communicated (explicitly)
in books and/or extensive surveys of the area.
For several years, we advocated the need for texts that focus on
the conceptual content of complexity theory, but it seems
that the only way of getting them written is to write them.
Put in other words, our feeling is that
the advocacy for a conceptual perspective of complexity theory
will be more effective if backed by a detailed textbook-level
exposition of the material. This is indeed the motivation for
the current book and its main governing principle.
This book offers a conceptual perspective on complexity theory,
and the presentation is designed to highlight this perspective.
It is intended mainly for students that wish to learn
complexity theory and for educators that intend to teach
a course on complexity theory. The book is also intended
to promote interest in complexity theory and make it
acccessible to general readers with adequate background
(which is mainly being comfortable with abstract discussions,
definitions and proofs).
We expect most readers to have a basic knowledge of algorithms,
or at least be fairly comfortable with the notion of an algorithm.
The conceptual perspectives offered in this book
are quite straightfoward (i.e., they follow directly
from known questions and studies in the field).
Indeed, the fundamental nature and conceptual content of the
questions and studies conducted in complexity theory is evident
to anybody who stops for a moment to think about it.
The problem, however, is that too few researchers stop to reflect
about this content, let alone communicate it to their students.
The annoying (and quite amazing) consequences are students that
have only a vague understanding of the meaning of these
fundamental notions and results.
In our opinion, it all boils down to taking the time to explicitly
discuss the meaning of definitions and results. A related issue
is using the ``right'' definitions (i.e., those that reflect
better the fundamental nature of the notion being defined)
and teaching things in the (conceptually) ``right'' order.
This book focuses on several sub-areas of complexity theory
(see the following organization and chapter summaries).
In each case, the exposition starts from the intuitive questions
addresses by the sub-area, as embodied in the concepts that it studies.
The exposition discusses the fundamental importance of these questions,
the choices made in the actual formulation of these questions and notions,
the approaches that underly the answers,
and the ideas that are embedded in these answers.
Our view is that these (``non-technical'') aspects are the core
of the field, and the presentation attempts to reflect this view.
We note that being guided by the conceptual contents of the material
leads, in some cases, to technical simplifications. Indeed,
for many of the results presented in this book, the presentation
of the proof is different (and arguablly easier to understand)
than the standard presentations.
Table of contents (tentative, Jan. 2006)
- Introduction and Preliminaries
1.1 Introduction
1.1.1 A brief overview of Complexity Theory;
1.1.2 Characteristics of Complexity Theory;
1.1.3 Contents of this book;
1.1.4 Approach and style of this book;
1.1.5 Standard notations and other conventions.
1.2 Computational Tasks and Models
1.2.1 Representation;
1.2.2 Computational Tasks;
1.2.3 Uniform Models (Algorithms)
[Turing machines, Uncomputable functions, Universal algorithms,
Time and space complexity, Oracle machines, Restricted models];
1.2.4 Non-uniform Models (Circuits and Advice)
[Boolean Circuits, Machines that take advice,
Restricted models];
1.2.5 Complexity Classes
Chapter Notes
- P, NP and NP-Completeness
2.1 The P versus NP Question
2.1.1 The search version - finding versus checking;
2.1.2 The decision version - proving versus verifying;
2.1.3 Equivalence of the two formulations;
2.1.4 The traditional definition of NP;
2.1.5 In support of P different from NP;
2.1.6 Two technical comments regarding NP.
2.2 Polynomial-time Reductions
2.2.1 The general notion of a reduction;
2.2.2 Reducing optimization problems to search problems;
2.2.3 Self-reducibility of search problems.
2.3 NP-Completeness
2.3.1 Definitions;
2.3.2 The existence of NP-complete problems;
2.3.3 Some natural NP-complete problems
[
Circuit and formula satisfiability - CSAT and SAT,
Combinatorics and graph theory];
2.3.4 NP sets that are neither in P nor NP-complete;
2.4 Three relatively advanced topics
2.4.1 Promise Problems;
2.4.2 Optimal search algorithms for NP;
2.4.3 The class coNP and its intersection with NP.
Chapter Notes
Exercises
- Variations on P and NP
3.1 Non-uniform polynomial-time (P/poly)
3.1.1 Boolean Circuits;
3.1.2 Machines that take advice.
3.2 The Polynomial-time Hierarchy (PH)
3.2.1 Alternation of quantifiers;
3.2.2 Non-deterministic oracle machines;
3.2.3 The P/poly-versus-NP Question and PH.
Chapter Notes
Exercises
- More Resources, More Power?
4.1 Non-uniform complexity hierarchies
4.2 Time Hierarchies and Gaps
4.2.1 Time Hierarchies
[The Time Hierarchy Theorem,
Impossibility of speed-up for universal computation,
Hierarchy theorem for non-deterministic time];
4.2.2 Time Gaps and Speed-Up
4.3 Space Hierarchies and Gaps
Chapter Notes
Exercises
- Space Complexity
5.1 General preliminaries
5.1.1 On the minimal amount of useful computation space;
5.1.2 Time versus Space
[Two composition lemmas, An obvious bound,
Subtleties regarding space-bounded reductions,
Complexity hierarchies and gaps,
Simultaneous time-space complexity];
5.1.3 Circuit Evaluation.
5.2 Logarithmic Space
5.2.1 The class L;
5.2.2 Log-Space Reductions;
5.2.3 Log-Space uniformity and stronger notions;
5.2.4 Undirected Connectivity.
5.3 Non-Deterministic Space Complexity
5.3.1 Two models;
5.3.2 NL and directed connectivity
[Completeness and beyond,
Relating NSPACE to DSPACE, Complementation or NL=coNL];
5.3.3 Discussion.
5.4 PSPACE and Games
Chapter Notes
Exercises
- Randomness and Counting
6.1 Probabilistic Polynomial-Time
6.1.1 Two-sided error (BPP);
6.1.2 One-sided error (RP and coRP);
6.1.3 Zero-sided error (ZPP);
6.1.4 Randomized Log-Space
[Definitional issues, the accidental tourist sees it all].
6.2 Counting
6.2.1 Exact Counting [including completeness];
6.2.2 Approximate Counting [for count-DNF and count-P];
6.2.3 Searching for unique solutions;
6.2.4 Uniform generation of solutions
[Relation to approximate counting,
Direct uniform generation].
Chapter Notes
Exercises
- The Bright Side of Hardness
7.1 One-Way Functions
7.1.1 The concept of one-way functions;
7.1.2 Amplification of Weak One-Way Functions;
7.1.3 Hard-Core Predicates.
7.2 Hard Predicates in E
7.2.1 Amplification wrt polynomial-size circuits
[From worst-case hardness to mild average-case hardness,
Yao's XOR Lemma, List decoding and hardness amplification];
7.2.2 Amplification wrt exponential-size circuits
[Hard regions, Hardness amplification via hard regions].
Chapter Notes
Exercises
- Pseudorandom Generators
8.1 Introduction
8.2 The General Paradigm
8.3 General-Purpose Pseudorandom Generators
8.3.1 The basic definition;
8.3.2 The archetypical application;
8.3.3 Computational Indistinguishability;
8.3.4 Amplifying the stretch function;
8.3.5 Constructions;
8.3.6 Non-uniformly strong pseudorandom generators;
8.3.7 Other variants and a conceptual discussion.
8.4 Derandomization of time-complexity classes
8.4.1 Definition;
8.4.2 Construction;
8.4.3 Variants and a conceptual discussion.
8.5 Space Pseudorandom Generators
8.5.1 Definitional issues;
8.5.2 Two constructions.
8.6 Special Purpose Generators
8.6.1 Pairwise-Independence Generators;
8.6.2 Small-Bias Generators;
8.6.3 Random Walks on Expanders.
Chapter Notes
Exercises
- Probabilistic Proof Systems
Introduction and Preliminaries
9.1 Interactive Proof Systems
9.1.1 Definition;
9.1.2 The Power of Interactive Proofs;
9.1.3 Variants and finer structure
[Arthur-Merlin games a.k.a public-coin proof systems,
Interactive proof systems with two-sided error,
A hierarchy of interactive proof systems,
Something completely different];
9.1.4 On computationally bounded provers
[How powerful should the prover be?
Computational-soundness].
9.2 Zero-Knowledge Proof Systems
9.2.1 Definitional Issues;
9.2.2 The Power of Zero-Knowledge;
9.2.3 Proofs of Knowledge - a parenthetical subsection.
9.3 Probabilistically Checkable Proof Systems
9.3.1 Definition;
9.3.2 The Power of Probabilistically Checkable Proofs
[Proving that PCP[poly,O(1)] contains NP,
Overview of the first proof of the PCP Theorem,
Overview of the second proof of the PCP Theorem];
9.3.3 PCP and Approximation;
9.3.4 More on PCP itself - an overview.
Chapter Notes
Exercises
- Relaxing the Requirements
10.1 Approximation
10.1.1 Search or Optimization;
10.1.2 Decision or Property Testing.
10.2 Average Case Complexity
10.2.1 The basic theory
[Definitional issues,
Complete problems, Probabilistic versions];
10.2.2 Ramifications
[Search versus Decision,
Simple versus sampleable distributions].
Chapter Notes
Exercises
Epilogue
Apdx A - Glossary of Complexity Classes
A.1 Introduction;
A.2 Algorithm-based classes
[Time complexity classes, Space complexity];
A.3 Circuit-based classes.
Apdx B - On the Quest for Lower Bounds
B.1 Preliminaries;
B.2 Boolean Circuit Complexity
[Basic Results and Questions,
Monotone Circuits,
Bounded-Depth Circuits,
Formula Size];
B.3 Arithmetic Circuits
[Univariate Polynomials,
Multivariate Polynomials];
B.4 Proof Complexity
[Logical Proof Systems,
Algebraic Proof Systems,
Geometric Proof Systems].
Apdx C - On the Foundations of Modern Cryptography
C.1 Introduction and Preliminaries;
C.2 Computational Difficulty;
C.3 Pseudorandomness
[including Pseudorandom Functions];
C.4 Zero-Knowledge
[The Simulation Paradigm,
The Actual Definition,
A construction and a generic application,
Variants and Issues];
C.5 Encryption Schemes
[Definitions,
Constructions,
Beyond Eavesdropping Security];
C.6 Signatures and Message Authentication
[Definitions,
Constructions,
Public-Key Infrastructure];
C.7 General Cryptographic Protocols
[The Definitional Approach and Some Models,
Some Known Results,
Construction Paradigms and Two Simple Protocols,
Concluding Remarks].
Apdx D - Probabilistic Preliminaries and Advanced Topics in Randomization
D.1 Probabilistic preliminaries
[Notational Conventions, Three Inequalities];
D.2 Hashing
[Definitions, Constructions, The Leftover Hash Lemma];
D.3 Sampling;
D.4 Randomness Extractors
[The Main Definition,
Extractors as averaging samplers,
Extractors as randomness-efficient error-reductions,
Other perspectives,
Constructions].
Apdx E - Explicit Constructions
E.1 Error Correcting Codes
[A mildly explicit version of the existential proof,
The Hadamard Code,
The Reed-Solomon Code,
The Reed-Muller Code,
Binary codes of constant relative distance and constant rate,
Two additional computational problems,
A list decoding bound];
E.2 Expander Graphs
[Two Mathematical Definitions,
Two levels of explicitness,
Two properties,
The Margulis-Gabber-Galil Expander,
The Iterated Zig-Zag Construction].
Apdx F - Some Omitted Proofs
F.1 Proving that PH reduces to count-P;
F.2 Proving that IP[O(f)] is contained in AM[O(f)] and in AM[f]
[Emulating general interactive proofs by AM-games,
Linear speed-up for AM]
Apdx G - Some Computational Problems
G.1 Graphs
G.2 Formulae
G.3 Algebra
G.4 Number Theory
Bibliography
Related Material Available on-line
Extracts from the preliminary draft of the book are available
as the numbered texts at my webpage
various expositions (1987-2006),
which contains also additional expositions.
The current book superseed previous
sets of lecture notes (1999 and 2002).
Additional closely related material includes
©Copyright 2006 by Oded Goldreich.
Permission to make copies of part or all of this work for personal
or classroom use is granted without fee provided that copies
are not made or distributed for profit or commercial
advantage and that new copies bear this notice and the full
citation on the first page. Abstracting with credit is permitted.
Back to Oded Goldreich's homepage.