Computational Complexity: A Conceptual Perspective

Oded Goldreich

cover

This book is rooted in the thesis that complexity theory is extremely rich in conceptual content, and that this contents should be explicitly communicated in expositions and courses on the subject. It focuses on several sub-areas of complexity theory, starting from the intuitive questions addresses by the sub-area. 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.

ISBN 978-0-521-88473-0
Published in US in May 2008.

Publisher: Cambridge University Press
(see the publisher's page for this volume).

Below is the book's tentative preface and Organization. Drafts (and additional related texts) are available from HERE. See also list of corrections and additions (to the print version).

Last updated: June 2008.

Preface (tentative, Jan. 2007)

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 a task of a particular type), 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 the computational resources required to solve a computational task (or a class of such tasks), rather than at a specific algorithm or an algorithmic schema. Actually, research in Complexity Theory tends to start with and focus on 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 computational 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 extremely appealing conceptual message, which can be appreciated also by non-experts. Furthermore, these conceptual aspects may be explained without entering 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 main thesis is that complexity theory is extremely rich in conceptual content, and that this contents should be explicitly communicated in expositions and courses on the subject. The desire to provide a corresponding textbook is indeed the motivation for writing 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 to serve as an introduction to the field, and can be used either as a textbook or for self-study. Indeed, the book's primary target audience consists of students that wish to learn complexity theory and 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 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 arguably easier to understand) than the standard presentations.

Table of contents (tentative, May 2007)

Preface, Orgnaization and Chapter Summaries, Acknowledgments
  1. 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
  2. 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 Two technical comments regarding NP; 2.1.5 The traditional definition of NP; 2.1.6 In support of P different from NP; 2.1.7 Philosophical meditations.
      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.2.4 Digest and general perspective.
      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.3.5 Reflections on complete problems.
      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
  3. 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
  4. 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
  5. Space Complexity
      5.1 General preliminaries and issues
        5.1.1 Important conventions; 5.1.2 On the minimal amount of useful computation space; 5.1.3 Time versus Space [Two composition lemmas, An obvious bound, Subtleties regarding space-bounded reductions, Serach vs Decision, Complexity hierarchies and gaps, Simultaneous time-space complexity]; 5.1.4 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 A retrospective discussion.
      5.4 PSPACE and Games
      Chapter Notes
      Exercises
  6. Randomness and Counting
      6.1 Probabilistic Polynomial-Time
        6.1.1 Basic modeling issues; 6.1.2 Two-sided error (BPP); 6.1.3 One-sided error (RP and coRP); 6.1.4 Zero-sided error (ZPP); 6.1.5 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
  7. 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.1.4 Reflections on Hardness Amplification.
      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
  8. Pseudorandom Generators
      Introduction
      8.1 The General Paradigm
      8.2 General-Purpose Pseudorandom Generators
        8.2.1 The basic definition; 8.2.2 The archetypical application; 8.2.3 Computational Indistinguishability; 8.2.4 Amplifying the stretch function; 8.2.5 Constructions; 8.2.6 Non-uniformly strong pseudorandom generators; 8.2.7 Stronger notions and conceptual reflections.
      8.3 Derandomization of time-complexity classes
        8.3.1 Defining canonical derandomizers; 8.3.2 Constructing canonical derandomizers; 8.3.3 Technical variations and conceptual reflections.
      8.4 Space Pseudorandom Generators
        8.4.1 Definitional issues; 8.4.2 Two constructions.
      8.5 Special Purpose Generators
        8.5.1 Pairwise-Independence Generators; 8.5.2 Small-Bias Generators; 8.5.3 Random Walks on Expanders.
      Chapter Notes
      Exercises
  9. Probabilistic Proof Systems
      Introduction and Preliminaries
      9.1 Interactive Proof Systems
        9.1.1 Motivation and Perspective; 9.1.2 Definition; 9.1.3 The Power of Interactive Proofs; 9.1.4 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.5 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
  10. 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 Preliminaries; 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, Algebraic, and Geometric Proof Systems].
    Apdx C - On the Foundations of Modern Cryptography
      C.1 Introduction and Preliminaries; C.2 Computational Difficulty [One-Way Functions and Trapdoor Permutations]; C.3 Pseudorandomness [including Pseudorandom Functions]; C.4 Zero-Knowledge [The Simulation Paradigm, The Actual Definition, A General Result and a Generic Application, Definitional Varitions and Related Notions]; C.5 Encryption Schemes [Definitions, Constructions, Beyond Eavesdropping Security]; C.6 Signatures and Message Authentication [Definitions, Constructions]; 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 [including Hitters]; 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

List of Corrections and Additions

The following list does not include errors that readers are likely to overcome by themselves. A partial list of such errors appear in HERE.

Back to Oded Goldreich's homepage.