Article

Separating the polynomial-time hierarchy by oracles

Author:

Andrew Chi-Chih YaoAuthors Info & Claims

SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer Science

Pages 1 - 10

https://doi.org/10.1109/SFCS.1985.49

Published: 21 October 1985 Publication History

Publisher Site

Abstract

We present exponential lower bounds on the size of depth-k Boolean circuits for computing certain functions. These results imply that there exists an oracle set A such that, relative to A, all the levels in the polynomial-time hierarchy are distinct, i.e., ΣkP,A is properly contained in Σk+1P,A for all k.

Cited By

View all

Nadimpalli SParham NVasconcelos FYuen HMohar BShinkar IO'Donnell R(2024)On the Pauli Spectrum of QAC0Proceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649662(1498-1506)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649662
Chen YLi JMohar BShinkar IO'Donnell R(2024)Hardness of Range Avoidance and Remote Point for Restricted Circuits via CryptographyProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649602(620-629)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649602
Chattopadhyay ELiao J(2023)Hardness against Linear Branching Programs and MoreProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.9(1-27)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.9
Show More Cited By

Index Terms

Separating the polynomial-time hierarchy by oracles
1. Theory of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Polynomial-Time Random Oracles and Separating Complexity Classes

Bennett and Gill [1981] showed that P^A ≠ NP^A ≠ coNP^A for a random oracle A, with probability 1. We investigate whether this result extends to individual polynomial-time random oracles. We consider two notions of random oracles: p-random oracles in the ...
Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy
The polynomial-time hierarchy and sparse oracles

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer Science

October 1985

553 pages

ISBN:0818608444

Publisher

IEEE Computer Society

United States

Publication History

Published: 21 October 1985

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

81
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nadimpalli SParham NVasconcelos FYuen HMohar BShinkar IO'Donnell R(2024)On the Pauli Spectrum of QAC0Proceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649662(1498-1506)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649662
Chen YLi JMohar BShinkar IO'Donnell R(2024)Hardness of Range Avoidance and Remote Point for Restricted Circuits via CryptographyProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649602(620-629)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649602
Chattopadhyay ELiao J(2023)Hardness against Linear Branching Programs and MoreProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.9(1-27)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.9
Harsha PMolli TShankar A(2023)Criticality of AC0-FormulaeProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.19(1-24)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.19
Kush DSaraf S(2023)Near-Optimal Set-Multilinear Formula Lower BoundsProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.15(1-33)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.15
Hatami PHoza WTal ATell RSaha BServedio R(2023)Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR TreesProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585216(895-904)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585216
Huang YIlango RRen HSaha BServedio R(2023)NP-Hardness of Approximating Meta-Complexity: A Cryptographic ApproachProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585154(1067-1075)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585154
Chen YHuang YLi JRen HSaha BServedio R(2023)Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs AlgorithmsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585147(1058-1066)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585147
Kush DSaraf S(2022)Improved low-depth set-multilinear circuit lower boundsProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.38(1-16)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.38
Lecomte VRamakrishnan PTan L(2022)The composition complexity of majorityProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.19(1-26)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.19
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

Polynomial-Time Random Oracles and Separating Complexity Classes

Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy

The polynomial-time hierarchy and sparse oracles

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations