Abstract
Several problems concerning superpolynomial size circuits and superpolynomial-time advice classes are investigated. First we consider the implications of NP (and other fundamental complexity classes) having circuits slighter bigger than polynomial. We prove that if such circuits exist, for example if NP has n logn size circuits, the exponential hierarchy collapses to the second level. Next we consider the consequences of the bottom levels of the exponential hierarchy being contained in small advice classes. Again various collapses result. For example, if EXP NP \(\subseteq\) EXP/poly then EXP NP =EXP.
This research was done while visiting the Boston University Computer Science Department with the support of NSF Grant CCR-8814339, The Netherlands Organization for Scientific research (NWO) grant SIR 13-603 and NWO-programma voor korte reisbeurzen.
Supported in part by National Science Foundation Grants CCR-8814339 and CCR-9103055.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Allender E. & O. Watanabe. Kolmogorov Complexity and Degrees of Tally Sets. Proc. Structure in Complexity Theory third annual conference, IEEE Computer Society Press (1988).
Babai L., L. Fortnow & C. Lund. Non-deterministic exponential time has twoprover interactive protocols. Proc. 31st IEEE Symp. on Foundations of Computer Science, (1990) pp16–25.
Balcázar J.L. Self-reducibilityi. Journal of Computer and System Sciences 41 (1990) pp367–388.
Balcázar J.L., J. Díaz & J. Gabarró. Structural Complexity I. W. Brauer, G. Rozenberg & A. Salomaa (eds.) EATCS Monographs on Theoretical Computer Science 11 (1988) Springer Verlag.
Feige U., S. Goldwasser, L. Lovász, S. Safra & M. Szegedy Approximating Clique is Almost NP-complete. Manuscript.
Hartmanis J., N. Immerman & V. Sewelson. Sparse Set in NP-P: EXPTIME versus NEXPTIME. Information and Control, 65 (1985) pp158–181.
Hemachandra L.A. Counting in Structural Complexity Theory. Ph.D. thesis Cornell University (1987).
Homer S. & L. Longpré. On Reductions of NP Sets to Sparse Sets. To appear in Proc. Structure in Complexity Theory sixth annual conference (1991) in Chigaco Il.
Kadin J. PNP[logn] and sparse Turing complete sets for NP. Proc. Structure in Complexity Theory second annual conference, IEEE Computer Society Press (1987) pp33–40.
Kannan R. Circuit-size Lower Bounds and Non-reducibility to Sparse Sets. Information and Control 55 (1982) pp40–46.
Karp, R.M. Reducibility among combinatorial problems. Complexity of Computer Computations, R.E. Miller & J.W. Thatcher eds. Plenum N.Y. pp85–103.
Karp, R.M. & R.J. Lipton. Some connections between nonuniform and uniform complexity classes. Proc. 21 st IEEE Found. Comput. Sci. (1980) pp302–309.
Mahaney S.R. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25 (1982) pp130–143.
Ogiwara M. & A. Lozano. On One Word-Decreasing Self-Reducible Sets. To appear in Proc. Sructure in Complexity Theory sixth annual conference (1991) in Chigaco Il.
Ogiware M. & O. Watanabe On polynomial time boounded truth-table reducibility of NP sets to sparse sets. Proc. 22nd Annual ACM Symposium on Theory of Computing (1990) pp457–467.
Wilson, C.B. Relativized Circuit Complexity J. Comp. Sys. Sci. 31 (1985) pp169–181.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buhrman, H., Homer, S. (1992). Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In: Shyamasundar, R. (eds) Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1992. Lecture Notes in Computer Science, vol 652. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56287-7_99
Download citation
DOI: https://doi.org/10.1007/3-540-56287-7_99
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56287-0
Online ISBN: 978-3-540-47507-1
eBook Packages: Springer Book Archive