Abstract
In 1990 Schapire gave an equivalent characterization of Levin's notion of functions, that are polynomial on average. This characterization gives a very smooth translation from worst case complexity to average case complexity of the notions for time and space complexity. We prove tight space and time hierarchy theorems and discuss the structure of deterministic and nondeterministic average case complexity classes.
The research of this author was supported by the Deutsche Forschungsgemeinschaft, grant No. Schö 302/4-1.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
J.L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I. Springer, 1988.
S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the theory of average case complexity. JCSS, 44(2):193–219, 1992.
R.V. Book. Tally languages and complexity classes. Inf. and Control, 26:281–287, 1974.
R.V. Book and D. Du. The existence and density of generalized complexity cores. J. ACM, 34(3):718–730, 1987.
J. Cai and A. Selman. Average time complexity classes. Technical Report TR95-019, ECCC Trier, 1995.
S.A. Cook. A hierarchy for nondeterministic time complexity. JCSS, 7:343–353, 1973.
M. Goldmann, P. Grape, and J. Håstad. On average time hierarchies. IPL, 49:15–20, 1994.
O. Goldreich. Towards a theory of average case complexity. Technical report, Technion Haifa, Israel, 1988.
Y. Gurevich. Average case complexity. JCSS, 42(3):346–398, 1991.
F. C. Hennie and R. E. Stearns. Two-tape simulation of multitape turing machines. J. ACM, 13(4):533–546, 1966.
R. Impagliazzo. A personal view of average-case complexity. In Proc. 10th STRUCTURE, pages 134–147, 1995.
C. Karg. Strukturfragen im Umfeld der Durchschnittskomplexität. Master's thesis, Universität Ulm, 1994.
K.I. Ko and H. Friedman. Computational complexity of real functions. TCS, 20:323–352, 1982.
L. Levin. Problems, complete in “average” instance. In Proc. 16th STOC, page 465, 1984.
L. Levin. Average case complete problems. SIAM J. Comput., 15:285–286, 1986.
R. Reischuk and C. Schindelhauer. Precise average case complexity. In Proc. 10th STACS, 1993.
R.E. Schapire. The emerging theory of average case complexity. Technical Report 431, MIT, 1990.
R. Schuler. Some properties of sets tractable under every polynomial-time computable distribution. IPL, 1995.
R. Schuler and O. Watanabe. Towards average-case complexity analysis of NP optimization problems. In Proc. 10th STRUCTURE, pages 148–159, 1995.
R. Schuler and T. Yamakami. Structural average case complexity. In Proc. 12th FST&TCS LNCS 652, pages 128–139, 1992.
R. Schuler and T. Yamakami. Sets computable in polynomial time on average. In Proc. 1st International Computing and Combinatorics Conference, 1995.
J. Wang and J. Belanger. On average P vs. average NP. In K. Ambos-Spies, S. Homer, and U. Schöning, editors, Complexity Theory—Current Research. Cambridge University Press, 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Karg, C., Schuler, R. (1995). Structure in average case complexity. In: Staples, J., Eades, P., Katoh, N., Moffat, A. (eds) Algorithms and Computations. ISAAC 1995. Lecture Notes in Computer Science, vol 1004. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0015409
Download citation
DOI: https://doi.org/10.1007/BFb0015409
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60573-7
Online ISBN: 978-3-540-47766-2
eBook Packages: Springer Book Archive