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
- Introduction
- Preliminaries
2.1 Computability and Algorithms;
2.2 Efficient Computability and the class P
- The P versus NP Question
3.1 Efficient Verification and the class NP;
3.2 The Big Conjecture;
3.3 NP versus coNP
- Reducibility and NP-Completeness
- Lower Bounds
5.1 Boolean Circuit Complexity;
5.2 Arithmetic Circuits;
5.3 Proof Complexity
- Randomized Computation
6.1 Counting at Random;
6.2 Probabilistic Proof Systems;
6.3 Weak Random Sources
- The Bright Side of Hardness
7.1 Pseudorandomness;
7.2 Cryptography
- The Tip of an Iceberg
8.1 Relaxing the Requirements;
8.2 Other Complexity Measures;
8.3 Other Notions of Computation
- 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.