article

Free access

The polynomial-time hierarchy and sparse oracles

Authors:

Jose L. Balcázar,

Ronald V. Book,

Uwe SchöningAuthors Info & Claims

Journal of the ACM (JACM), Volume 33, Issue 3

Pages 603 - 617

https://doi.org/10.1145/5925.5937

Published: 01 May 1986 Publication History

PDF eReader

Abstract

Questions about the polynomial-time hierarchy are studied. In particular, the questions, “Does the polynomial-time hierarchy collapse?” and “Is the union of the hierarchy equal to PSPACE?” are considered, along with others comparing the union of the hierarchy with certain probabilistic classes. In each case it is shown that the answer is “yes” if and only if for every sparse set S, the answer is “yes” when the classes are relativized to S if and only if there exists a sparse set S such that the answer is “yes” when the classes are relativized to S. Thus, in each case the question is answered if it is answered for any arbitrary sparse oracle set.

Long and Selman first proved that the polynomial-time hierarchy collapses if and only if for every sparse set S, the hierarchy relative to S collapses. This result is re-proved here by a different technique.

References

[1]

ANGLUIN, D. On counting problems and the polynomial-time hierarchy. Theor. Comput. Sci. 12 (1980), 161-173.

Google Scholar

[2]

BAKER, T., GILL, J., AND SOLOVAY, R. Relativizations of the P =? NP question. SIAM J. Comput. 4 (1975), 431-442.

Google Scholar

[3]

BALC,~ZAR, J., BOOK, R. AND SCHONING, U. On bounded query machines. Theor. Comput. Sci. 40(1985).

Crossref

Google Scholar

[4]

BERMAN, L., AND HARTMANIS, J. On isomorphisms and density of NP and other complete sets. SIAM J. Comput. 6 (1977), 305-322.

Google Scholar

[5]

BOOK, R., AND LONG, T. Relativizing the P -? NP problem. Submitted for publication.

Google Scholar

[6]

BOOK, R., AND WRATHALL, C. Bounded query machines: On NP() and NPQUERY(). Theor. Comput. Sci. 15 (1981 ), 41-50.

Google Scholar

[7]

BOOK, R., LONG, T., AND SELMAN, A. Quantitative relativizations of complexity classes. SIAM J. Comput. 13 (1984), 461-487.

Crossref

Google Scholar

[8]

GILL, J. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977), 675-695.

Google Scholar

[9]

KARP, R., AND LIPTON, R. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th ACM Symposium on Theory of Computing. ACM, New York, 1980, pp. 302-309. An extended version has also appeared: Turing machines that take advice. In L'Enseignement Math~matique, 2nd series 28, 1982, pp. 191-209.

Crossref

Google Scholar

[10]

Ko, K. On self-reducibility and weak P-selectivity. ~ Comput. Syst. Sci. 26 (1983), 209-221.

Google Scholar

[11]

Ko, K., AND SCHONING, U. On circuit-size complexity and the low hierarchy in NP. SIAM J. Comput. 14 (1985), 41-51.

Google Scholar

[12]

LONG, T. A note on sparse oracles for NP. J. Comput. Syst. Sci. 24 (1982), 224-232.

Google Scholar

[13]

LONG, T. On restricting access to oracles compared with restricting access to oracles. SIAM J. Comput. 14 (1985), 585-597.

Google Scholar

[14]

LONG, T., AND SELMAN, A. Relativizing complexity classes with sparse oracles. J. ACM 33, 3 (July 1986), 618-627.

Crossref

Google Scholar

[15]

MAHANEY, S. Sparse complete sets for NP: Solution to a conjecture of Berman and Hartmanis. J. Comput. Syst. Sci. 25 (1982), 130-143.

Google Scholar

[16]

MAHANEY, S. Sparse sets and reducibilities. In Studies in Complexity Theory, R. Book, Ed. Research Notes in Theoretical Computer Science, Pitman, London, England, 1986, pp. 63-118.

Google Scholar

[17]

MEYER, A., AND PATERSON, M. With what frequency are apparently intractable problems difficult? Tech. Rep., M.I.T., Cambridge, Mass., Feb. 1979.

Google Scholar

[18]

PAPADIMITRIOU, C. On the complexity of unique solutions. In Proceedings of the 23rd IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 1982, pp. 14-20.

Google Scholar

[19]

SAVITCH, W. Relationships between deterministic and nondeterministic space complexities. J. Comput. Syst. Sci. 4 (1970), 177-192.

Google Scholar

[20]

SCHNORR, C. Optimal algorithms for self-reducible problems. In Automata, Languages, and Programming, S. Michaelson and R. Milner, Eds. Edinburgh University Press, Edinburgh, Scotland, 1976, pp. 322-337.

Google Scholar

[21]

SCHONING, U. On small generators. Theort. Comput. Sci. 34 (1984), 337-341.

Google Scholar

[22]

SIMON, J. On some central problems in computational complexity. Ph.D. dissertation, Dept. of Comput. Sci., Cornell University, Ithaca, N.Y., 1975.

Crossref

Google Scholar

[23]

STOCKMEYER, L. The polynomial-time hierarchy. Theort. Comput. Sci. 3 (1976), 1-22.

Google Scholar

[24]

VALIANT, L. On the complexity of computing the permanent. Theor. Comput. Sci. 8 (1979), 189-202.

Google Scholar

[25]

VALIANT, L. The complexity of enumeration and reliability problems. SIAM J. Comput. 8 (1979), 410-421.

Google Scholar

[26]

WRATHALL, C. Complete sets and the polynomial-time hierarchy. Theor. Comput. Sci. 3 (1976), 23-33.

Google Scholar

[27]

YAO, A. Separating the polynomial-time hierarchy by oracles. In Proceedings of the 26th IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 1985, pp. 1-10.

Crossref

Google Scholar

[28]

YAP, C. Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 27 (1983), 287-300.

Google Scholar

Cited By

View all

Kwisthout J(2018)Approximate inference in Bayesian networks: Parameterized complexity resultsInternational Journal of Approximate Reasoning10.1016/j.ijar.2017.10.02993(119-131)Online publication date: Feb-2018
https://doi.org/10.1016/j.ijar.2017.10.029
Mau DCozman F(2017)The effect of combination functions on the complexity of relational Bayesian networksInternational Journal of Approximate Reasoning10.1016/j.ijar.2017.03.01485:C(178-195)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.ijar.2017.03.014
Hemaspaandra L(2014)Beautiful structuresACM SIGACT News10.1145/2670418.267043645:3(54-70)Online publication date: 17-Sep-2014
https://dl.acm.org/doi/10.1145/2670418.2670436
Show More Cited By

Index Terms

The polynomial-time hierarchy and sparse oracles
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Models of computation

Recommendations

Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to ...
The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection

We show that if the Boolean hierarchy collapses to level $k$, then the polynomial hierarchy collapses to $BH_{3}(k)$, where $BH_{3}(k)$ is the $k$th level of the Boolean hierarchy over $\Sigma^{P}_{2}$. This is an improvement over the known results, ...

Reviews

Reviewer: Graham Ernest Farr

Concerning the question of whether or not the Polynomial Hierarchy (PH) of Meyer and Stockmeyer is indeed an infinite hierarchy of distinct classes, the authors prove: (1)If k ?9T2, then the Polynomial Hierarchy collapses to &Sgr; p-k- if and only if for every sparse set S the polynomial hierarchy relative to S collapses to &Sgr; p-k-( S). (2)The Polynomial Hierarchy is a proper infinite hierarchy if and only if for every sparse set S the Polynomial Hierarchy relative to S is a proper infinite hierarchy. Result (1) was proved first, by a related technique, in a paper by Long and Selman [1] that appears in the same issue and can be regarded as a companion paper to the one under review. If the oracle set does not have to be sparse, then there are relativizations of PH that are infinite [2] and other relativizations of PH that collapse. At present such results do not appear to tell us much about the unrelativized PH. If the oracle is sparse, however, results (1) and (2) directly relate to the collapsing or otherwise of the relativized and unrelativized Polynomial Hierarchies. Thus, it would suffice to answer our opening question relative to any sparse oracle set. Similar results are found, by the same techniques, for the questions of whether PH equals PSPACE, whether Valiant's counting class D#P is contained in PH, and whether Gill's probabilistic class PP is contained in PH. The first two of these questions were also studied in the same vein in [1]. Long and Selman also obtain results analogous to result (1) for relativizations of the P=__ __NP and NP=__ __ co-NP questions with tally sets as oracles. The main results of this paper and [1] are the first of their kind, although it is worth noting another current line of research in which the model of relativized computation (rather than the oracle set) is restricted. Some results similar in flavor to those discussed here have been obtained. (See, for example, Book's recent survey [3].) The paper under review is an interesting and worthwhile contribution to the theory of relativized complexity classes. It contains a full discussion of the results and of related work by others.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 33, Issue 3

July 1986

219 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/5925

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1986

Published in JACM Volume 33, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

78
Total Citations
View Citations
850
Total Downloads

Downloads (Last 12 months)80
Downloads (Last 6 weeks)14

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kwisthout J(2018)Approximate inference in Bayesian networks: Parameterized complexity resultsInternational Journal of Approximate Reasoning10.1016/j.ijar.2017.10.02993(119-131)Online publication date: Feb-2018
https://doi.org/10.1016/j.ijar.2017.10.029
Mau DCozman F(2017)The effect of combination functions on the complexity of relational Bayesian networksInternational Journal of Approximate Reasoning10.1016/j.ijar.2017.03.01485:C(178-195)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.ijar.2017.03.014
Hemaspaandra L(2014)Beautiful structuresACM SIGACT News10.1145/2670418.267043645:3(54-70)Online publication date: 17-Sep-2014
https://dl.acm.org/doi/10.1145/2670418.2670436
Ben Daniel S(2012)On the Advice Complexity of TournamentsComputing and Combinatorics10.1007/978-3-642-32241-9_40(470-481)Online publication date: 2012
https://doi.org/10.1007/978-3-642-32241-9_40
Zuckerman MFaliszewski PBachrach YElkind E(2008)Manipulating the quota in weighted voting gamesProceedings of the 23rd national conference on Artificial intelligence - Volume 110.5555/1619995.1620031(215-220)Online publication date: 13-Jul-2008
https://dl.acm.org/doi/10.5555/1619995.1620031
Faliszewski PHemaspaandra L(2008)The Complexity of Power-Index ComparisonProceedings of the 4th international conference on Algorithmic Aspects in Information and Management10.1007/978-3-540-68880-8_18(177-187)Online publication date: 23-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-68880-8_18
Goldsmith JOgihara MRothe J(2006)Tally NP sets and easy census functionsMathematical Foundations of Computer Science 199810.1007/BFb0055798(483-492)Online publication date: 28-May-2006
https://doi.org/10.1007/BFb0055798
Cai JChakaravarthy VHemaspaandra LOgihara M(2005)Competing provers yield improved Karp–Lipton collapse resultsInformation and Computation10.1016/j.ic.2005.01.002198:1(1-23)Online publication date: Apr-2005
https://doi.org/10.1016/j.ic.2005.01.002
Köbler JWatanabe O(2005)New collapse consequences of NP having small circuitsAutomata, Languages and Programming10.1007/3-540-60084-1_74(196-207)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-60084-1_74
Li HLi G(2005)Nonuniform lowness and strong nonuniform lownessAlgorithms and Computation10.1007/3-540-58325-4_227(593-599)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-58325-4_227
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy

Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses

The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations