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 online.

A preliminary draft (dated January 2006): in
gzip .ps
format and in six parts corresponding to chapters
02,
35,
67,
89,
10B,
C.
See also related material
and errata.

Partial revisions:
Chap.
79 and Apdx C (June 2006),
Chap.
6 & 10 and Apdx D (July 2006),
Sec 1.2
and Chap. 2 (Sept. 2006),
Chap. 35
and Apdx E (Oct. 2006),
Preface
and Sec. 1.1 (Oct. 2006),
Preface,
Chap. 1 & 10, and Ref. (Dec. 2006).

A full revision (dated December 2006): in a single file
gzip .ps
format.

Latest avaiblabe revisions:
Chap 02
(Dec. 2006),
Chap 35
(Jan. 2007),
Chap 67
(Feb. 2007),
Chap 78
(Mar. 2007),
Chap 910
(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 (halfcentury) 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 ``lowlevel''
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 ``highlevel'' study of computation.
The theory of NPcompleteness 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 ``highlevel'' 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 nonexperts.
Furthermore, these conceptual aspects may be explained
without entering into excessive technical detail.
Consequently, the ``highlevel'' direction is more suitable
for an exposition in a book of the current nature.
Finally, there is a subjective reason:
the ``highlevel'' direction is within our own expertise,
while this cannot be said about the ``lowlevel'' 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 textbooklevel
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 subareas of complexity theory
(see the following organization and chapter summaries).
In each case, the exposition starts from the intuitive questions
addresses by the subarea, 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 (``nontechnical'') 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 Nonuniform Models (Circuits and Advice)
[Boolean Circuits, Machines that take advice,
Restricted models];
1.2.5 Complexity Classes
Chapter Notes
 P, NP and NPCompleteness
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 Polynomialtime Reductions
2.2.1 The general notion of a reduction;
2.2.2 Reducing optimization problems to search problems;
2.2.3 Selfreducibility of search problems.
2.3 NPCompleteness
2.3.1 Definitions;
2.3.2 The existence of NPcomplete problems;
2.3.3 Some natural NPcomplete problems
[
Circuit and formula satisfiability  CSAT and SAT,
Combinatorics and graph theory];
2.3.4 NP sets that are neither in P nor NPcomplete;
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 Nonuniform polynomialtime (P/poly)
3.1.1 Boolean Circuits;
3.1.2 Machines that take advice.
3.2 The Polynomialtime Hierarchy (PH)
3.2.1 Alternation of quantifiers;
3.2.2 Nondeterministic oracle machines;
3.2.3 The P/polyversusNP Question and PH.
Chapter Notes
Exercises
 More Resources, More Power?
4.1 Nonuniform complexity hierarchies
4.2 Time Hierarchies and Gaps
4.2.1 Time Hierarchies
[The Time Hierarchy Theorem,
Impossibility of speedup for universal computation,
Hierarchy theorem for nondeterministic time];
4.2.2 Time Gaps and SpeedUp
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 spacebounded reductions,
Complexity hierarchies and gaps,
Simultaneous timespace complexity];
5.1.3 Circuit Evaluation.
5.2 Logarithmic Space
5.2.1 The class L;
5.2.2 LogSpace Reductions;
5.2.3 LogSpace uniformity and stronger notions;
5.2.4 Undirected Connectivity.
5.3 NonDeterministic 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 PolynomialTime
6.1.1 Twosided error (BPP);
6.1.2 Onesided error (RP and coRP);
6.1.3 Zerosided error (ZPP);
6.1.4 Randomized LogSpace
[Definitional issues, the accidental tourist sees it all].
6.2 Counting
6.2.1 Exact Counting [including completeness];
6.2.2 Approximate Counting [for countDNF and countP];
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 OneWay Functions
7.1.1 The concept of oneway functions;
7.1.2 Amplification of Weak OneWay Functions;
7.1.3 HardCore Predicates.
7.2 Hard Predicates in E
7.2.1 Amplification wrt polynomialsize circuits
[From worstcase hardness to mild averagecase hardness,
Yao's XOR Lemma, List decoding and hardness amplification];
7.2.2 Amplification wrt exponentialsize circuits
[Hard regions, Hardness amplification via hard regions].
Chapter Notes
Exercises
 Pseudorandom Generators
8.1 Introduction
8.2 The General Paradigm
8.3 GeneralPurpose 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 Nonuniformly strong pseudorandom generators;
8.3.7 Other variants and a conceptual discussion.
8.4 Derandomization of timecomplexity 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 PairwiseIndependence Generators;
8.6.2 SmallBias 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
[ArthurMerlin games a.k.a publiccoin proof systems,
Interactive proof systems with twosided error,
A hierarchy of interactive proof systems,
Something completely different];
9.1.4 On computationally bounded provers
[How powerful should the prover be?
Computationalsoundness].
9.2 ZeroKnowledge Proof Systems
9.2.1 Definitional Issues;
9.2.2 The Power of ZeroKnowledge;
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 Algorithmbased classes
[Time complexity classes, Space complexity];
A.3 Circuitbased classes.
Apdx B  On the Quest for Lower Bounds
B.1 Preliminaries;
B.2 Boolean Circuit Complexity
[Basic Results and Questions,
Monotone Circuits,
BoundedDepth 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 ZeroKnowledge
[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,
PublicKey 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 randomnessefficient errorreductions,
Other perspectives,
Constructions].
Apdx E  Explicit Constructions
E.1 Error Correcting Codes
[A mildly explicit version of the existential proof,
The Hadamard Code,
The ReedSolomon Code,
The ReedMuller 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 MargulisGabberGalil Expander,
The Iterated ZigZag Construction].
Apdx F  Some Omitted Proofs
F.1 Proving that PH reduces to countP;
F.2 Proving that IP[O(f)] is contained in AM[O(f)] and in AM[f]
[Emulating general interactive proofs by AMgames,
Linear speedup for AM]
Apdx G  Some Computational Problems
G.1 Graphs
G.2 Formulae
G.3 Algebra
G.4 Number Theory
Bibliography
Related Material Available online
Extracts from the preliminary draft of the book are available
as the numbered texts at my webpage
various expositions (19872006),
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.