Complexity Theory - A Survey

Oded Goldreich

Material available on-line: a PSfile (400KB, written in 2000). [in PDF].

See also a related survey by Oded and Avi Wigderson, 2004.

From the Introduction

Computational Complexity (a.k.a Complexity Theory) is a central field of Computer Science with a remarkable list of celebrated achievements as well as a very vibrant research activity. The field is concerned with the study of the intrinsic complexity of computational tasks, and this study tend to aim at generality: It focuses on natural computational resources, and considers the effect of limiting these resources on the class of problems that can be solved.

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 (or effect) 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 on either of the problems (or notions) being related. The current exposition focuses on the latter effort (or direction), which may be viewed as a ``high-level'' study of computation. We present a few of the interesting notions, results and open problems in this direction.

We list several reasons for our choice to focus on the ``high-level'' direction. The first is the great conceptual significance of the know results; that is, as we shall see, many known results (and open problems) in this direction have an appealing conceptual message, which can be appreciated also by non-experts. Furthermore, these conceptual aspects may be explained without getting into too much technical details. Finally, we admit that the ``high-level'' direction is within the author's expertise, while this cannot be said about the ``low-level'' direction.

Survey's Outline

Preliminaries: Computability.
The P versus NP Question: search and decision versions.
NP-Completeness
Randomized Computation
- Probabilistic Polynomial-Time
- Counting at Random
- Probabilistic Proof Systems (IP, ZK and PCP)
The Bright Side of Hardness
- Pseudorandomness
- Cryptography
The Tip of an Iceberg
- Average-case complexity and approximation problems
- Other complexity measures and other notions of computation
- Major areas we have ignored

Related Material (by Oded Goldreich)

Back to Oded Goldreich's homepage.

Copyright (C symbol) 1999 by Oded Goldreich. Permission to make digital or hard 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.

This work may be published or be a basis for publication in the future. Copyright may be transferred without further notice and this version may no longer be accessible.