Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-058 | 2nd December 1997 00:00

Notes on Levin's Theory of Average-Case Complexity.

RSS-Feed




TR97-058
Authors: Oded Goldreich
Publication: 4th December 1997 10:33
Downloads: 1650
Keywords: 


Abstract:


In 1984, Leonid Levin has initiated a theory of average-case complexity.
We provide an exposition of the basic definitions suggested by Levin,
and discuss some of the considerations underlying these definitions.



ISSN 1433-8092 | Imprint