Article

Free access

Relativized polynomial time hierarchies having exactly K levels

Author:

Ker-I KoAuthors Info & Claims

STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing

Pages 245 - 253

https://doi.org/10.1145/62212.62235

Published: 01 January 1988 Publication History

PDF eReader

References

[1]

D. Angluin, On counting problems and the polynomial time hierarchy, Theoret. Cornput. Sci. 12 (1980), 161-173.

Crossref

Google Scholar

[2]

T. Baker, J. Gill and R. Solovay, Relativizations of the P-?NP question, SIAM J. comput. 4 (1975), 431-442.

Google Scholar

[3]

T. Baker and A. Selman, A second step toward the polynomial llierarchy, Theoret. Cornpnt. ScJ. 8 (1979), t77-187.

Google Scholar

[4]

M. Furst, J. Saxe and M. Sipser, Parity, circuits, and the polynomial time hierarchy, Math. Systems Theory 17 (1984), 13-27.

Crossref

Google Scholar

[5]

J. T. Hastad, Computational Limitations/'or Sma//- Depth Circuits, (Ph.D. Dissertation, MIT), MIT Press, Cambridge, 1987.

Digital Library

Google Scholar

[6]

J. T. Hastad, Almost optimal lower bounds for small depth circuits, Proc. of ISth A(TM Syrup. a, Theory of C. oml~uting (1986), 6-20.

Digital Library

Google Scholar

[7]

H. Heller, Relativizcd polynolnial hierarchies extending two levels, Math. systems Theory 17 (19s4), 7~-s4.

Google Scholar

[8]

J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

Digital Library

Google Scholar

[9]

M. Sipser, Borel sets and circuit complexity, Proc. of 15th A CM Syrup. on Theory of Computing (10s3), 61-69.

Digital Library

Google Scholar

[10]

L. Stockmeyer, The polynomial-time hierarchy, Theoret. Comput. Sei. 3 (1977), 1--22.

Crossref

Google Scholar

[11]

C. Wrathatl, Co,nplcte sets and the 1)olyno,nial hicrarclly, 'l'!tc~rct. (5~nll~,tt. Sci. 3 (1977), 23-33.

Google Scholar

[12]

A. Yao, Separating the l~olyJ,t, tldal~tilne iticrarchy by oracles, l~ro~, ot' 26th IEEE $~vn,t,. ~, l, bundations of Computer Science (1985), t 10.

Digital Library

Google Scholar

Cited By

View all

Jin RWu WThai MDu D(2021)Black-Box and Data-Driven ComputationBlack Box Optimization, Machine Learning, and No-Free Lunch Theorems10.1007/978-3-030-66515-9_6(163-168)Online publication date: 4-Jan-2021
https://doi.org/10.1007/978-3-030-66515-9_6
Du DWang J(2020)In Memoriam: Ker-I Ko (1950–2018)Complexity and Approximation10.1007/978-3-030-41672-0_1(1-7)Online publication date: 21-Feb-2020
https://doi.org/10.1007/978-3-030-41672-0_1
Hartmanis JChang RRanjan DRohatgi P(2005)Structural complexity theory: Recent surprisesSWAT 9010.1007/3-540-52846-6_73(1-12)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-52846-6_73
Show More Cited By

Index Terms

Relativized polynomial time hierarchies having exactly K levels
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
    2. Complexity theory and logic

Recommendations

A Relationship between Difference Hierarchies and Relativized Polynomial Hierarchies.
Collapsing recursive oracles for relativized polynomial hierarchies
FCT'05: Proceedings of the 15th international conference on Fundamentals of Computation Theory

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) ...
Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing

January 1988

553 pages

ISBN:0897912640

DOI:10.1145/62212

Chairman:
J'anos Simon
Univ. of Chicago, Illinois

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 January 1988

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC88

Sponsor:

SIGACT

STOC88: 1988 Symposium on the Theory of Computing

May 2 - 4, 1988

Illinois, Chicago, USA

Acceptance Rates

STOC '88 Paper Acceptance Rate 53 of 192 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
353
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)9

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jin RWu WThai MDu D(2021)Black-Box and Data-Driven ComputationBlack Box Optimization, Machine Learning, and No-Free Lunch Theorems10.1007/978-3-030-66515-9_6(163-168)Online publication date: 4-Jan-2021
https://doi.org/10.1007/978-3-030-66515-9_6
Du DWang J(2020)In Memoriam: Ker-I Ko (1950–2018)Complexity and Approximation10.1007/978-3-030-41672-0_1(1-7)Online publication date: 21-Feb-2020
https://doi.org/10.1007/978-3-030-41672-0_1
Hartmanis JChang RRanjan DRohatgi P(2005)Structural complexity theory: Recent surprisesSWAT 9010.1007/3-540-52846-6_73(1-12)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-52846-6_73
Hemachandra L(1988)Structure of complexity classes: Separations, collapses, and completenessMathematical Foundations of Computer Science 198810.1007/BFb0017131(59-72)Online publication date: 1988
https://doi.org/10.1007/BFb0017131

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

A Relationship between Difference Hierarchies and Relativized Polynomial Hierarchies.

Collapsing recursive oracles for relativized polynomial hierarchies

Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy