Article

Competing Provers Yield Improved Karp-Lipton Collapse Results

Authors:

Venkatesan T. Chakaravarthy,

Lane A. Hemaspaandra,

Mitsunori OgiharaAuthors Info & Claims

STACS '03: Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science

Pages 535 - 546

Published: 27 February 2003 Publication History

Abstract

Via competing provers, we show that if a language A is self-reducible and has polynomial-size circuits then S ₂ ^A = S ₂. Building on this, we strengthen the K mper-AFK Theorem, namely, we prove that if NP (NP coNP)/poly then the polynomial hierarchy collapses to S ₂ ^{NP coNP}. We also strengthen Yap's Theorem, namely, we prove that if NP coNP/poly then the polynomial hierarchy collapses to S ₂ ^NP. Under the same assumptions, the best previously known collapses were to ZPP ^NP and ZPP ^NP ^NP respectively ([20,6], building on [18,1,17,30]). It is known that S ₂ ZPP ^NP [8]. That result and its relativized version show that our new collapses indeed improve the previously known results. Since the K mper-AFK Theorem and Yap's Theorem are used in the literature as bridges in a variety of results--ranging from the study of unique solutions to issues of approximation--our results implicitly strengthen all those results.

References

[1]

M. Abadi, J. Feigenbaum, and J. Kilian. On hiding information from an oracle. Journal of Computer and System Sciences , 39:21-50, 1989.

[2]

V. Arvind, Y. Han, L. Hemachandra, J. Köbler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Schöning, R. Silvestri, and T. Thierauf. Reductions to sets of low information content. In K. Ambos-Spies, S. Homer, and U. Schöning, editors, Complexity Theory , pages 1-45. Cambridge University Press, 1993.

[3]

J. Balcázar, R. Book, and U. Schöning. The polynomial-time hierarchy and sparse oracles. Journal of the ACM , 33(3):603-617, 1986.

[4]

J. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I . EATCS Texts in Theoretical Computer Science. Springer-Verlag, 2nd edition, 1995.

[5]

J. Balcázar and U. Schöning. Logarithmic advice classes. Theoretical Computer Science , 99(2):279-290, 1992.

[6]

N. Bshouty, R. Cleve, S. Kannan, R. Gavaldä, and C. Tamon. Oracles and queries that are sufficient for exact learning. In Proceedings of the 17th ACM Conference on Computational Learning Theory , pages 130-139, 1994. JCSS 52(3):421-433 (1996).

[7]

H. Buhrman and L. Fortnow, Sept. 2001. Personal communication.

[8]

J. Cai. S ₂ ^p ¿ ZPP ^NP. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science , pages 620-629. IEEE Computer Society Press, Oct. 2001.

[9]

J. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara. Some Karp-Lipton-type theorems based on S ₂. Technical Report TR-759, Department of Computer Science, Univ. of Rochester, Rochester, NY, Sept. 2001. Revised, Nov. 2002. Available (as the TR-759 entry) at http://www.cs.rochester.edu/trs/theory-trs.html.

[10]

R. Canetti. More on BPP and the polynomial-time hierarchy. Information Processing Letters , 57(5):237-241, 1996.

[11]

R. Gavaldà and J. Balcázar. Strong and robustly strong polynomial time reducibilities to sparse sets. Theoretical Computer Science , 88(1):1-14, 1991.

[12]

J. Hartmanis and L. Hemachandra. Complexity classes without machines: On complete languages for UP. Theoretical Computer Science , 58(1-3):129-142, 1988.

[13]

L. Hemaspaandra, S. Jain, and N. Vereshchagin. Banishing robust Turing completeness. International Journal of Foundations of Computer Science , 4(3):245- 265, 1993.

[14]

L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman. Computing solutions uniquely collapses the polynomial hierarchy. SIAM Journal on Computing , 25(4):697-708, 1996.

[15]

L. Hemaspaandra and M. Ogihara. The Complexity Theory Companion . Springer-Verlag, 2002.

[16]

J. Hopcroft. Recent directions in algorithmic research. In Proceedings 5th GI Conference on Theoretical Computer Science , pages 123-134. Springer-Verlag Lecture Notes in Computer Science #104 , 1981.

[17]

J. Kämper. Non-uniform proof systems: A new framework to describe non-uniform and probabilistic complexity classes. Theoretical Computer Science , 85(2):305-331, 1991.

[18]

R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th ACM Symposium on Theory of Computing , pages 302-309. ACM Press, Apr. 1980. An extended version has also appeared as: Turing machines that take advice, L'Enseignement Mathématique , 2nd series, 28, 1982, pages 191-209.

[19]

J. Köbler. On the structure of low sets. In Proceedings of the 10th Structure in Complexity Theory Conference , pages 246-261. IEEE Computer Society Press, June 1995.

[20]

J. Köbler and O.Watanabe. New collapse consequences of NP having small circuits. SIAM Journal on Computing , 28(1):311-324, 1998.

[21]

T. Long. Strong nondeterministic polynomial-time reducibilities. Theoretical Computer Science , 21:1-25, 1982.

[22]

C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. Journal of the ACM , 39(4):859-868, 1992.

[23]

A. Russell and R. Sundaram. Symmetric alternation captures BPP. Computational Complexity , 7(2):152-162, 1998.

[24]

J. Simon. On Some Central Problems in Computational Complexity . PhD thesis, Cornell University, Ithaca, N.Y., Jan. 1975. Available as Cornell Department of Computer Science Technical Report TR75-224.

[25]

S. Toda. PP is as hard as the polynomial hierarchy. SIAM Journal on Computing , 20(5):865-877, 1991.

[26]

S. Toda and M. Ogihara. Counting classes are at least as hard as the polynomial-time hierarchy. SIAM Journal on Computing , 21(2):316-328, 1992.

[27]

V. Variyam. A note on NP ¿ coNP/poly. Technical Report RS-00-19, BRICS, Aarhus, Denmark, Aug. 2000. Note: The author uses NP ¿ coNP/poly to denote what in the present paper is denoted (NP ¿ coNP)/poly.

[28]

V. Variyam. AM _exp ¿ (NP ¿ coNP) / poly. Manuscript, Oct. 2002.

[29]

K. Wagner. The complexity of combinatorial problems with succinct input representations. Acta Informatica , 23(3):325-356, 1986.

[30]

C. Yap. Some consequences of non-uniform conditions on uniform classes. Theoretical Computer Science , 26(3):287-300, 1983.

Cited By

Pavan ASelman ASengupta SVinodchandran N(2007)Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchyTheoretical Computer Science10.1016/j.tcs.2007.06.013385:1-3(167-178)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1016/j.tcs.2007.06.013
Fortnow LOgihara M(2006)Very sparse leaf languagesProceedings of the 31st international conference on Mathematical Foundations of Computer Science10.1007/11821069_33(375-386)Online publication date: 28-Aug-2006
https://dl.acm.org/doi/10.1007/11821069_33
Chakaravarthy VRoy S(2006)Oblivious symmetric alternationProceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science10.1007/11672142_18(230-241)Online publication date: 23-Feb-2006
https://dl.acm.org/doi/10.1007/11672142_18
Show More Cited By

Competing Provers Yield Improved Karp-Lipton Collapse Results
1. Theory of computation
  1. Computational complexity and cryptography
  2. Models of computation
    1. Computability

Recommendations

Competing Provers Yield Improved Karp-Lipton Collapse Results
Competing provers yield improved Karp-Lipton collapse results

Via competing provers, we show that if a language A is self-reducible and has polynomial-size circuits then S"2^A=S"2. Building on this, we strengthen the Kamper-AFK theorem, namely, we prove that if NP@?(NP@?coNP)/poly then the polynomial hierarchy ...
A tight Karp-Lipton collapse result in bounded arithmetic

Cook and Krajíček have recently obtained the following Karp-Lipton collapse result in bounded arithmetic: if the theory PV proves NP⊆ P/poly, then the polynomial hierarchy collapses to the Boolean hierarchy, and this collapse is provable in PV. Here we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

STACS '03: Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science

February 2003

698 pages

ISBN:3540006230

Editors:
Helmut Alt,
Michel Habib

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 27 February 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pavan ASelman ASengupta SVinodchandran N(2007)Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchyTheoretical Computer Science10.1016/j.tcs.2007.06.013385:1-3(167-178)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1016/j.tcs.2007.06.013
Fortnow LOgihara M(2006)Very sparse leaf languagesProceedings of the 31st international conference on Mathematical Foundations of Computer Science10.1007/11821069_33(375-386)Online publication date: 28-Aug-2006
https://dl.acm.org/doi/10.1007/11821069_33
Chakaravarthy VRoy S(2006)Oblivious symmetric alternationProceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science10.1007/11672142_18(230-241)Online publication date: 23-Feb-2006
https://dl.acm.org/doi/10.1007/11672142_18
Cai JChakaravarthy V(2005)A Note on Zero Error Algorithms Having Oracle Access to One NP QueryProceedings of the 11th Annual International Conference on Computing and Combinatorics - Volume 359510.5555/2958119.2958223(339-348)Online publication date: 16-Aug-2005
https://dl.acm.org/doi/10.5555/2958119.2958223

View Options

View options

Figures

Tables

Media

View Table of Conten