Abstract
We present two new complexity classes which are based on a complexity class C and an error probability function F. The first, F-Err C, reflects the (weak) feasibility of problems that can be computed within the error bound F. As a more adequate measure to investigate lower bounds we introduce F-Errio C where the error is infinitely often bounded by the function F. These definitions generalize existing models of feasible erroneous computations and cryptographic intractability.
We identify meaningful bounds for the error function and derive new diagonalizing techniques. These techniques are applied to known time hierarchies to investigate the influence of error bound. It turns out that in the limit a machine with slower running time cannot predict the diagonal language within a significantly smaller error prob. than 1/2.
Further, we investigate two classical non-recursive problems: the halting problem and the Kolmogorov complexity problem. We present strict lower bounds proving that any heuristic algorithm claiming to solve one of these problems makes unrecoverable errors with constant probability. Up to now it was only known that infinitely many errors will occur.
parts of this work are supported by a stipend of the “Gemeinsames Hochschulsonderprogramm III von Bund und Länder” through the DAAD.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Ben-David, B. Chor, O. Goldreich, M. Luby, On the Theory of Average Case Complexity, Journal of Computer and System Sciences, Vol. 44, 1992, 193–219. 395, 395
R. Book, D. Du, The Existence and Density of Generalized Complexity Cores, Journal of the ACM, Vol. 34, No. 3, 1987, 718–730. 404
J-Y. Cai and A. Selman, Fine separation of average time complexity classes, SIAM Journal on Computing, Vol. 28(4), 1999, 1310–1325. 395, 400
Martin Davis, Hillary Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM, 1960, 201–215. 395
B. Fagin, Fast Addition for Large Integers, IEEE Tr. Comput. Vol. 41, 1992, 1069–1077. 396
P. Gemmel, M. Horchol Tight Bounds on Expected Time to Add Correctly and Add Mostly Correctly, Inform. Proc. Letters, 1994, 77–83. 396
M. Goldmann, P. Grape and J. Håstad. On average time hierarchies, Information Processing Letters, Vol. 49(1), 1994, 15–20. 400
S. Goldwasser, S. Micali, Probabilistic Encryption & How to Play Mental Poker Keeping Secret All Partial Information, Proc. 14th Annual ACM Symposium on Theory of Computing, 1982, 365–377. 398
S. Goldwasser, S. Micali, R. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, SIAM J. Comput. Vol.17, No. 2, 1988, 281–308. 397
Y. Gurevich, Average Case Completeness, Journal of Computer and System Sciences, Vol. 42, 1991, 346–398. 395
H. Hoos, Stochastic Local Search-Methods, Models, Applications, Dissertation, Technical University Darmstadt, 1998. 395
R. Impagliazzo, Hard-core distributions for somewhat hard problems, In 36th Annual Symposium on Foundations of Computer Science, 1995, 538-545. 398
R. Impagliazzo, A personal view of average-case complexity, In Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 134–147, 1995. 395
R. Impagliazzo, A. Wigderson, Randomness vs. Time: De-randomization under a uniform assumption, Proc. 39th Symposium on Foundations of Computer Science, 1998, 734–743. 396, 396
Leonid Levin, Average Case Complete Problems, SIAM Journal on Computing, Vol. 15, 1986, 285–286. 395, 395
M. Li, P. Vitáni, An Introduction to Kolmogorov Complexity and its Application, Springer, 1997. 400
P. W. Purdom, C. A. Brown, The Pure Literal Rule and Polynomial Average Time, SIAM J. Comput., 1985, 943–953. 395
J. Reif, Probabilistic Parallel Prefix Computation, Comp. Math. Applic. 26, 1993, 101–110. Technical Report Havard University, 1983. 396
R. Reischuk, C. Schindelhauer, An Average Complexity Measure that Yields Tight Hierarchies, Journal on Computional Complexity, Vol. 6, 1996, 133-173. 395, 400
C. Schindelhauer, Average-und Median-Komplexitätsklassen, Dissertation, Medizinische Universität Lübeck, 1996. 396, 396, 396
C. Schindelhauer, A. Jakoby, Computational Error Complexity Classes, Technical Report A-97-17, Medizinische Universität Lübeck, 1997. 396, 396
U. Schöning, P. Orponen, The Structure of Polynomial Complexity Cores, Proc. 11th Symposium MFCS, LNCS 176, 1984, 452–458. 404
R. Schuler, O. Watanabe, Towards Average-Case Complexity Analysis of NP Optimization Problems, Proc. 10th Annual IEEE Conference on Structure in Complexity Theory, 1995, 148–159. 395
Bart Selman, Hector Levesque, David Mitchell, Hard and Easy Distributions of SAT Problems, Proc. 10. Nat. Conf. on Artificial Intelligence, 1992, 440–446. 395
C. Smith, A Recursive Introduction to the Theory of Computation, Springer, 1994. 401
T. Yamakami, Average Case Computational Complexity Theory, Phd. Thesis, Technical Report 307/97, Department of Computer Science, University of Toronto. 396, 396, 397
T. Yamakami, Polynomial Time Samplable Distributions, Proc.Mathematical Foundations of Computer Science, 1996, 566–578. 396, 396, 397
Y. Yesha, On certain polynomial-time truth-table reducibilities of complete sets to sparse sets, SIAM Journal on Computing, Vol. 12(3), 1983, 411–425. 404
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schindelhauer, C., Jakoby, A. (1999). The Non-recursive Power of Erroneous Computation. In: Rangan, C.P., Raman, V., Ramanujam, R. (eds) Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1999. Lecture Notes in Computer Science, vol 1738. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46691-6_32
Download citation
DOI: https://doi.org/10.1007/3-540-46691-6_32
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66836-7
Online ISBN: 978-3-540-46691-8
eBook Packages: Springer Book Archive