zbMATH — the first resource for mathematics

Average case complexity, revisited. (English) Zbl 1343.68114
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 422-450 (2011).
Summary: More than two decades elapsed since Levin set forth a theory of average-case complexity. In this survey we present the basic aspects of this theory as well as some of the main results regarding it. The current presentation deviates from our old [“Notes on Levin’s theory of average-case complexity”, ibid. 6650, 233–247 (2011; Zbl 1343.68111)] in several aspects. In particular:
We currently view average-case complexity as referring to the performance on “average” (or rather typical) instances, and not as the average performance on random instances. (Thus, it may be more justified to refer to this theory by the name typical-case complexity, but we retain the name average-case for historical reasons.)
We include a treatment of search problems, and a presentation of the reduction of “NP with sampleable distributions” to “NP with P-computable distributions” (due to R. Impagliazzo and L. A. Levin [“No better ways to generate hard NP instances than picking uniformly at random”, in: Proceedings of the 31st annual symposium on foundations of computer science, FOCS 1990. St. Louis, MO: IEEE. 812–821 (1990; doi:10.1109/FSCS.1990.89604)].
We include N. Livne’s result [Comput. Complexity 19, No. 4, 477–499 (2010; Zbl 1213.68315)] by which all natural NPC-problems have average-case complete versions. This result seems to shed doubt on the association of P-computable distributions with natural distributions.

For the entire collection see [Zbl 1220.68005].

68Q25 Analysis of algorithms and problem complexity
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68-02 Research exposition (monographs, survey articles) pertaining to computer science
PDF BibTeX Cite
Full Text: DOI
[1] Ben-David, S., Chor, B., Goldreich, O., Luby, M.: On the Theory of Average Case Complexity. JCSS 44(2), 193–219 (1992) · Zbl 0762.68027
[2] Bogdanov, A., Trevisan, L.: Average-case complexity. Foundations and Trends in Theoretical Computer Science 2(1) (2006) · Zbl 1143.68401
[3] Cook, S.A.: The Complexity of Theorem Proving Procedures. In: 3rd STOC, pp. 151–158 (1971)
[4] Goldreich, O.: Notes on Levin’s Theory of Average-Case Complexity. In: Goldreich, O., et al.: Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 424–454. Springer, Heidelberg (2011); See also ECCC, TR97-058 (December 1997) · Zbl 1343.68111
[5] Goldreich, O.: Foundation of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001) · Zbl 1007.94016
[6] Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge (2008) · Zbl 1154.68056
[7] Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A Pseudorandom Generator from any One-way Function. SICOMP 28(4), 1364–1396 (1999); Combines papers of Impagliazzo et al., 21st STOC (1989) and Håstad 22nd STOC (1990) · Zbl 0940.68048
[8] Impagliazzo, R., Levin, L.A.: No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. In: 31st FOCS, pp. 812–821 (1990)
[9] Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
[10] Levin, L.A.: Average Case Complete Problems. SICOMP 15, 285–286 (1986) · Zbl 0589.68032
[11] Livne, N.: All Natural NPC Problems Have Average-Case Complete Versions. In: ECCC, TR06-122 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.