Abstract
We show that under some truth-table oracle B there are almost exponential gaps in the (infinite often) hierarchy of bounded-error probabilistic time, in particular BPP Btt = ZPTIME Btt (n). This proves a main theorem in [5], which is extended to the theoretical limit.
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
Allender, Beigel, Hertrampf, Homer, Almost-everywhere Complexity Hierarchies for Nondeterministic Time, TCS 115(1993), pp. 225–241.
Balcazar, Diaz, Gabarro, Structural Complexity 2, Springer 1990.
Berg, Håstad, On the BPP Hierarchy Problem, Technical Report TRITA-NA9702, Royal Inst. of Technology, Stockholm 1997.
Freivalds, Probabilistic two-way Machines, Proc. MFCS, LNCS 118, Springer 1981, pp. 33–45.
Fortnow, Sipser, Probabilistic Computation and Linear Time, ACM Symposium on Theory of Computing (STOC), 1989, pp. 148–156.
Fortnow, Sipser, Retraction of Probabilistic Computation and Linear Time, ACM Symposium on Theory of Computing (STOC), 1997, p. 750.
Hemaspaandra, Complexity Theory Column 11, SIGACT News 26,4 (1995), pp. 5–15.
Karpinski, Verbeek, On the Monte Carlo Space Constructible Functions and Separation Results for Probabilistic Complexity Classes, Information and Computation 75 (1987), pp. 178–189.
Karpinski, Verbeek, Randomness, Provability and the Separation of Monte Carlo Time and Space, Computation Theory and Logic, LNCS 270 (1987), pp. 189–207.
Rettinger, Orakelabhängige Zeithierarchiesätze, PhD thesis, FernUniversität Hagen, 1999.
Rackoff, Seiferas, Limitations on Separating Nondeterministic Complexity Classes, SIAM Journal on Computing 10 (1981), pp. 742–745.
Seiferas, Fischer, Meyer, Separating Nondeterministic Time Complexity Classes, JACM 25, pp. 146–167.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rettinger, R., Verbeek, R. (2001). Monte-Carlo Polynomial versus Linear Time - The Truth-Table Case. In: Freivalds, R. (eds) Fundamentals of Computation Theory. FCT 2001. Lecture Notes in Computer Science, vol 2138. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44669-9_30
Download citation
DOI: https://doi.org/10.1007/3-540-44669-9_30
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42487-1
Online ISBN: 978-3-540-44669-9
eBook Packages: Springer Book Archive