Article

Free access

The PL hierarchy collapses

Author:

Mitsunori OgiharaAuthors Info & Claims

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

Pages 84 - 88

https://doi.org/10.1145/237814.237834

Published: 01 July 1996 Publication History

PDF eReader

References

[1]

E. Allender and M. Ogihara. Relationships among PL, ~L, and the determinant. In Proceedings of the 9th Conference on Structure in Complexity Theory, pages 267-278. IEEE Computer Society Press, 1994.

Crossref

Google Scholar

[2]

R. Beigel. Personal communication.

Google Scholar

[3]

T. Baker, J. Gill, and R. Solovay. Relativizations of the 79 =?AFT) question. SIAM Journal on Computing, 4(4):431-442, 1975.

Crossref

Google Scholar

[4]

R. Beigel, N. Reingold, and D. Spielman. PP is closed under intersection. Journal of Computer and System $ctences, 50:191-202, 1995.

Digital Library

Google Scholar

[5]

S. Fenner, L. Fortnow, and S. Kurtz. Gapdefinable counting classes. Journal of Computer and System Sciences, 48(1):116-148, 1994.

Digital Library

Google Scholar

[6]

L. Fortnow and N. Reingold. PP is closed under truth-table reductions. Information and Computation, 124:1-6, 1996.

Digital Library

Google Scholar

[7]

J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675-695, 1977.

Digital Library

Google Scholar

[8]

N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17:935-938, 1988.

Digital Library

Google Scholar

[9]

H. Jung. On probabilistic time and space. In Proceedings of the 12th Conference on Automata, Languages and Programming, pages 310- 317. Springer-Verlag Lecture Notes,n Computer Sczence ~194{, 1985.

Digital Library

Google Scholar

[10]

R. Ladner and N. Lynch. Relativization of questions about logspace computability. Mathematical Systems Theory, 10(1):19-32, 1976.

Crossref

Google Scholar

[11]

D. Newman. Rational approximation to Ixl. Mich,. gan Mathematics Journal, 11:11-14, 1964.

Google Scholar

[12]

S. Paturi and M. Saks. Approximating threshold circuits by rational functions. Informatwn and Computation, 112(2):257-272, 1994.

Digital Library

Google Scholar

[13]

C. Rackoff and J. Seiferas. Limitations on separating nondeterministic complexity classes. SIAM Journal on Computing, 10(4):742-745, 1981.

Crossref

Google Scholar

[14]

W. Ruzzo, J. Simon, and M. Tompa. Spacebounded hierarchies and probabilistic computations. Journal of Computer and System Sciences, 28:216-230, 1984.

Crossref

Google Scholar

[15]

i. Simon. On some subrecurs,ve reducibilities. PhD thesis, Stanford University, 1977. Available as Computer Science Department Stanford University Technical Report STAN-CS-77-608.

Digital Library

Google Scholar

[16]

R. Szelepcs~nyi. The method of forced enumeration for nondeterministic automata. A cta Informatica, 26:279-284, 1988.

Digital Library

Google Scholar

Cited By

View all

Allender EOgihara M(2011)Relationships among $PL$, $\#L$, and the determinantRAIRO - Theoretical Informatics and Applications10.1051/ita/199630010001130:1(1-21)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1996300100011
Allender EReinhardt K(1998)Isolation, matching, and countingProceedings. Thirteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat. No.98CB36247)10.1109/CCC.1998.694594(92-100)Online publication date: 1998
https://doi.org/10.1109/CCC.1998.694594
Beigel RFu B(1997)Circuits Over PP and PLProceedings of the 12th Annual IEEE Conference on Computational Complexity10.5555/791230.792282Online publication date: 24-Jun-1997
https://dl.acm.org/doi/10.5555/791230.792282
Show More Cited By

Index Terms

The PL hierarchy collapses
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Computing Solutions Uniquely Collapses the Polynomial Hierarchy

Is there an NP function that, when given a satisfiable formula as input, outputs one satisfying assignment uniquely? That is, can a nondeterministic function cull just one satisfying assignment from a possibly exponentially large collection of ...
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 PL Hierarchy Collapses

It is shown that the PL hierarchy PLH = PL ,\bigcup\limits\, PL^PL ,\bigcup\limits\, PL^PL^PL ,\bigcup\limits\, \cdots$, defined in terms of the Ruzzo--Simon--Tompa relativization, collapses to PL.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

July 1996

661 pages

ISBN:0897917855

DOI:10.1145/237814

Chairman:
Gary L. Miller

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC96

Sponsor:

SIGACT

STOC96: ACM Symposium on Theory of Computing

May 22 - 24, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

STOC '96 Paper Acceptance Rate 74 of 201 submissions, 37%;

Overall Acceptance Rate 1,438 of 4,499 submissions, 32%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
285
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)7

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Allender EOgihara M(2011)Relationships among $PL$, $\#L$, and the determinantRAIRO - Theoretical Informatics and Applications10.1051/ita/199630010001130:1(1-21)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1996300100011
Allender EReinhardt K(1998)Isolation, matching, and countingProceedings. Thirteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat. No.98CB36247)10.1109/CCC.1998.694594(92-100)Online publication date: 1998
https://doi.org/10.1109/CCC.1998.694594
Beigel RFu B(1997)Circuits Over PP and PLProceedings of the 12th Annual IEEE Conference on Computational Complexity10.5555/791230.792282Online publication date: 24-Jun-1997
https://dl.acm.org/doi/10.5555/791230.792282
Reinhardt KAllender E(1997)Making nondeterminism unambiguousProceedings 38th Annual Symposium on Foundations of Computer Science10.1109/SFCS.1997.646113(244-253)Online publication date: 1997
https://doi.org/10.1109/SFCS.1997.646113
Beigel RBin Fu (1997)Circuits over PP and PLProceedings of Computational Complexity. Twelfth Annual IEEE Conference10.1109/CCC.1997.612297(24-35)Online publication date: 1997
https://doi.org/10.1109/CCC.1997.612297
Allender EBeals ROgihara MMiller G(1996)The complexity of matrix rank and feasible systems of linear equations (extended abstract)Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing10.1145/237814.237856(161-167)Online publication date: 1-Jul-1996
https://dl.acm.org/doi/10.1145/237814.237856

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.

Cited By

Index Terms

Recommendations

Computing Solutions Uniquely Collapses the Polynomial Hierarchy

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

The PL Hierarchy Collapses