Strong self-reducibility precludes strong immunity
From MaRDI portal
Publication:4895818
DOI10.1007/BF01184814zbMath0857.68046MaRDI QIDQ4895818
Hemaspaandra, Lane A., Marius Zimand
Publication date: 3 March 1997
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Related Items (6)
Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ A new algorithm design technique for hard problems ⋮ P-immune sets with holes lack self-reducibility properties. ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation ⋮ A second step towards complexity-theoretic analogs of Rice's Theorem ⋮ Resource bounded immunity and simplicity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bi-immunity results for cheatable sets
- On the construction of parallel computers from various basis of Boolean functions
- Random oracles separate PSPACE from the polynomial-time hierarchy
- Simplicity, immunity, relativizations and nondeterminism
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- Are there interactive protocols for co-NP languages?
- Random languages for nonuniform complexity classes
- Generic oracles, uniform machines, and codes
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- The generic oracle hypothesis is false
- The random oracle hypothesis is false
- An oracle builder's toolkit
- Defying upward and downward separation
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
- On the random oracle hypothesis
- Notions of weak genericity
- Immunity, Relativizations, and Nondeterminism
- A note on separating the relativized polynomial time hierarchy by immune sets
- Bi-immune sets for complexity classes
- Relativizations of Unambiguous and Random Polynomial Time Classes
- Complexity Measures for Public-Key Cryptosystems
- The Boolean Hierarchy I: Structural Properties
- The Boolean Hierarchy II: Applications
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Near-Testable Sets
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- A note on balanced immunity
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Computational Complexity of Probabilistic Turing Machines
- BANISHING ROBUST TURING COMPLETENESS
- IP = PSPACE
- On closure properties of bounded two-sided error complexity classes
- Easily Checked Generalized Self-Reducibility
This page was built for publication: Strong self-reducibility precludes strong immunity
