Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets

DOI10.1016/0304-3975(92)90232-5MaRDI QIDQ1199689zbMATH OpenOpenAlexWikidataFDO

Authors Danilo Bruschi

Publication date 16 January 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(92)90232-5

zbMATH Keywords

relativizationstrong separations

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

Two classes of sets \(C_ 1\) and \(C_ 2\) are strongly separated if there is an infinite set \(A\) in \(C_ 2\) which is immune for \(C_ 1\), that means no infinite subset of \(A\) is in \(C_ 1\). Strong separations are shown, in a relativized setting, for virtually all pairs of classes of the polynomial-time hierarchy. This paper combines several previously known nontrivial techniques (in a non-trivial way), essentially such steming from lower bound proofs for bounded-depth circuits (involving probabilistic arguments).

Recommendations

• A second step toward the strong polynomial-time hierarchy
• A note on separating the relativized polynomial time hierarchy by immune sets
• scientific article; zbMATH DE number 4077187
• Defying upward and downward separation
• scientific article; zbMATH DE number 4114605

Cites work

• A note on separating the relativized polynomial time hierarchy by immune sets
• A second step toward the polynomial hierarchy
• Complete sets and the polynomial-time hierarchy
• scientific article; zbMATH DE number 3988707 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3586480 (Why is no real title available?)
• Immunity, Relativizations, and Nondeterminism
• Oracle-dependent properties of the lattice of NP sets
• Parity, circuits, and the polynomial-time hierarchy
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Relativized polynomial hierarchies extending two levels
• Simplicity, immunity, relativizations and nondeterminism
• Simplicity, Relativizations and Nondeterminism
• The polynomial-time hierarchy

Cited in

(19)

• Random oracles separate PSPACE from the polynomial-time hierarchy
• The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\)
• Separating complexity classes with tally oracles
• Relating polynomial time to constant depth
• Separation of complexity classes in Koiran's weak model
• Separating classes in the exponential-time hierarchy from classes in PH
• Defying upward and downward separation
• Generic separations
• Quantum and classical complexity classes: Separations, collapses, and closure properties
• Resource bounded immunity and simplicity
• STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
• A note on separating the relativized polynomial time hierarchy by immune sets
• Nonlevelable sets and immune sets in the accepting density hierarchy inNP
• scientific article; zbMATH DE number 3988707 (Why is no real title available?)
• scientific article; zbMATH DE number 4125012 (Why is no real title available?)
• Immunity and Simplicity for Exact Counting and Other Counting Classes
• Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems
• scientific article; zbMATH DE number 2163013 (Why is no real title available?)
• Strong self-reducibility precludes strong immunity

This page was built for publication: Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199689)