Abstract
Lower bounds for the first levels of the exponential time hierarchy with respect to circuit and advice classes are studied. Using time bounded Kolmogorov complexity, languages are constructed which witness that various exponential time classes are not included in (fixed) polynomial advice classes. We show as well that these languages are not included in small circuit families where the circuits are of a fixed, polynomial size. The results yield optimal bounds (up to relativization) on efficient nonuniform computation.
Research partially supported by the National Science Foundation under grants CCR-9103055 and CCR-9400229.
Research partially supported by the National Science Foundation under grant CCR-9410713.
We thanks Jack Lutz for referring us to his previous work and pointing out the relationships to the results in Section 2.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity, volume I. Springer-Verlag, New York, 1988.
J. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity, volume II. Springer-Verlag, New York, 1990.
L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. In Proc. 6th IEEE Structure in Complexity Theory, pages 213–219, 1991.
H. Buhrman and S. Homer. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In Proc. of the Conf. on Foundations of Software Technology and Theoretical Computer Science, 1992.
J. Díaz and J. Torán. Classes of bounded nondeterminism. Math. Systems Theory, 23:21–32, 1990.
B. Fu. With quasi-linear queries, EXP is not polynomial time Turing reducible to sparse sets. In Proc. IEEE Structure in Complexity Theory, pages 185–191, 1993.
R. Gavaldà and O. Watanabe. On the computational complexity of small descriptions. In Proc. 6th IEEE Structure in Complexity Theory, pages 89–101, 1991.
L. Hemachandra. Counting in structural complexity theory. Ph.D. Thesis, Cornell University, 1987.
J. Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. In Proc.24th Annual FOCS Conference, pages 439–445, 1983.
R. Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control, 55:40–46, 1982.
C. M. R. Kintala and P. C. Fischer. Refining nondeterminism in relativized polynomial-time bounded computations. SIAM Journal on Computing, 9:46–53, 1980.
R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In Proc. 12th ACM Symposium on Theory of Computing, pages 302–309, 1980.
J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, pages 220–258, 1992.
J. H. Lutz. One-way functions and balanced NP. Unpublished manuscript.
J. H. Lutz and E. Mayordomo. Measure, stochasticity, and the density of hard languages. SIAM Journal on Computing, to appear.
S. E. Mocas. Separating exponential time classes from polynomial time classes. Ph.D. Thesis, Northeastern University, 1993.
C. H. Papadimitriou and M. Yannakakis. On limited nondeterminism and the complexity of the v-c dimension. In Proc. 8th IEEE Structure in Complexity Theory, pages 12–18, 1993.
U. Schöning. Complexity and Structure, volume 211 of Lecture Notes in Computer Science. Springer-Verlag, New York, 1985.
C. B. Wilson. Relativized circuit complexity. Journal Computer Systems Sci., 31:169–181, 1985.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Homer, S., Mocas, S. (1995). Nonuniform lower bounds for exponential time classes. In: Wiedermann, J., Hájek, P. (eds) Mathematical Foundations of Computer Science 1995. MFCS 1995. Lecture Notes in Computer Science, vol 969. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60246-1_122
Download citation
DOI: https://doi.org/10.1007/3-540-60246-1_122
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60246-0
Online ISBN: 978-3-540-44768-9
eBook Packages: Springer Book Archive