Collapsing recursive oracles for relativized polynomial hierarchies
Pages 149 - 160
Abstract
Certain recursive oracles can force the polynomial hierarchy to collapse to any fixed level. All collections of such oracles associated with each collapsing level form an infinite hierarchy, called the collapsing recursive oracle polynomial (CROP) hierarchy. This CROP hierarchy is a significant part of the extended low hierarchy (note that the assumption P = NP makes the both hierarchies coincide). We prove that all levels of the CROP hierarchy are distinct by showing “strong” types of separation. First, we prove that each level of the hierarchy contains a set that is immune to its lower level. Second, we show that any two adjacent levels of the CROP hierarchy can be separated by another level of the CROBPP hierarchy—a bounded-error probabilistic analogue of the CROP hierarchy. Our proofs extend the circuit lower-bound techniques of Yao, Håstad, and Ko.
References
[1]
E. Allender and L. Hemachandra. Lower bounds for the low hierarchy. J. ACM 39 (1992) 234-251.
[2]
T. Baker, J. Gill, and R. Solovay. Relativizations of the P=?NP question. SIAM J. Comput. 4 (1975) 431-442.
[3]
J. L. Balcázar, R. V. Book, and U. Schöning. Sparse sets, lowness, and highness. SIAM J. Comput. 15 (1986) 739-747.
[4]
J. L. Balcázar, R. V. Book, and U. Schöning. The polynomial-time hierarchy and sparse oracles. J. ACM 33 (1986) 603-617.
[5]
D. Bruschi. Strong separations of the polynomial hierarchy with oracles: constructive separations by immune and simple sets. Theoret. Comput. Sci. 102 (1992) 215-252.
[6]
J. Cai, V. T. Chakaravarthy, L. A. Hemaspaandra, M. Ogihara. Some Karp-Liptontype theorems based on S2. Technical Report, 2001.
[7]
J. D. Håstad. Computational Limitations for Small-Depth Circuits. Ph.D. dissertation, Massachusetts Institute of Technology, 1987.
[8]
H. Heller. Relativized polynomial hierarchies extending two levels. Math. Systems Theory 17 (1984) 71-84.
[9]
K. Ko. Relativized polynomial time hierarchies having exactly k levels. SIAM J. Comput. 18 (1989) 392-408.
[10]
K. Ko. Separating and collapsing results on the relativized probabilistic polynomial time hierarchy. J. ACM 37 (1990) 415-438.
[11]
T. Long and A. Selman. Relativizing complexity classes with sparse oracles. J. ACM 33 (1986) 618-627.
[12]
T. J. Long and M. Sheu. A refinement of the low and high hierarchies. Math. Systems Theory 28 (1995) 299-327.
[13]
A. Meyer and L. Stockmeyer. The equivalence problem for regular expression with squaring requires exponential time. In Proc. 13th IEEE Symposium on Switching and Automata Theory, pp.125-129, 1972.
[14]
U. Schöning. Complete sets and closeness to complexity classes. Math. Systems Theory 19 (1986) 29-41.
[15]
U. Schöning. Probabilistic complexity classes and lowness. J. Comput. System Sci. 39 (1989) 84-100.
[16]
M. Sheu and T. J. Long. The extended low hierarchy is an infinite hierarchy. SIAM J. Comput. 23 (1994) 488-509.
[17]
L. Stockmeyer. On approximation algorithms for #P. SIAM J. Comput. 14 (1985) 849-861.
[18]
R. E. Wilber. Randomness and the density of hard problems. In Proc. 24th Annual Symposium on Foundations of Computer Science, pp.335-342, 1983.
[19]
T. Yamakami and T. Suzuki. Resource bounded immunity and simplify. To appear in Theoret. Comput. Sci., An extended abstract appeared in Proc. 3rd IFIP Intern. Conf. Theoretical Computer Science (Exploring New Frontiers of Theoretical Informatics), Kluwer Academic Publishers, pp.81-95, 2004.
[20]
A. C. Yao. Separating the polynomial-time hierarchy by oracles. Proc. 26th IEEE Symposium on Foundations of Computer Science, pp.1-10, 1985.
Index Terms
- Collapsing recursive oracles for relativized polynomial hierarchies
Index terms have been assigned to the content through auto-classification.
Recommendations
Relativized collapsing between BPP and PH under stringent oracle access
We propose a new model of stringent oracle access defined for a general complexity class. For example, when comparing the power of two machine models relative to some oracle set X, we restrict that machines of both types ask queries from the same segment ...
Oracles That Compute Values
This paper focuses on complexity classes of partial functions that are computed in polynomial time with oracles in NPMV, the class of all multivalued partial functions that are computable nondeterministically in polynomial time. Concerning deterministic ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 17 August 2005
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Dec 2024