# 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
2.1 Computability and Algorithms; 2.2 Efficient Computability and the class P
3. The P versus NP Question
3.1 Efficient Verification and the class NP; 3.2 The Big Conjecture; 3.3 NP versus coNP
4. Reducibility and NP-Completeness
5. Lower Bounds
5.1 Boolean Circuit Complexity; 5.2 Arithmetic Circuits; 5.3 Proof Complexity
6. Randomized Computation
6.1 Counting at Random; 6.2 Probabilistic Proof Systems; 6.3 Weak Random Sources
7. The Bright Side of Hardness
7.1 Pseudorandomness; 7.2 Cryptography
8. The Tip of an Iceberg
8.1 Relaxing the Requirements; 8.2 Other Complexity Measures; 8.3 Other Notions of Computation
9. Concluding Remarks
Bibliography
Appendix: Glossary of Complexity Classes
A.1 Algorithm-based classes; A.2 Circuit-based 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.