Complexity Theory - A Survey

Oded Goldreich and Avi Wigderson


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


Preface

The strive for efficiency is ancient and universal, as time is always short for humans. Computational Complexity is a mathematical study of the what can be achieved when time (and other resources) are scarce.

In this brief article we will introduce quite a few notions: Formal models of computation, and measures of efficiency; the P vs. NP problem and NP-completeness; circuit complexity and proof complexity; randomized computation and pseudorandomness; probabilistic proof systems, cryptography and more. A glossary of complexity classes is included in an appendix. We highly recommend the given bibliography and the references therein for more information.

Organization

  1. Introduction
  2. Preliminaries
  3. The P versus NP Question
  4. Reducibility and NP-Completeness
  5. Lower Bounds
  6. Randomized Computation
  7. The Bright Side of Hardness
  8. The Tip of an Iceberg
  9. Concluding Remarks
    Bibliography
    Appendix: Glossary of Complexity Classes

Related Material (by Oded Goldreich)


Back to Oded Goldreich's homepage.


Copyright (C symbol) 2004 by Oded Goldreich and Avi Wigderson. 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.