Strong self-reducibility precludes strong immunity
From MaRDI portal
Recommendations
- Immunity properties and strong positive reducibilities
- Resource bounded immunity and simplicity
- scientific article; zbMATH DE number 2163012
- Mathematical Foundations of Computer Science 2005
- Autoreducibility, mitoticity, and immunity
- A reducibility related to being hyperimmune-free
- Immune Logics ain't that Immune
- scientific article; zbMATH DE number 4022646
- Self-reducibility
- Immunity properties of the s-degrees
Cites work
- A note on balanced immunity
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
- A note on separating the relativized polynomial time hierarchy by immune sets
- An oracle builder's toolkit
- Are there interactive protocols for co-NP languages?
- BANISHING ROBUST TURING COMPLETENESS
- Bi-immune sets for complexity classes
- Bi-immunity results for cheatable sets
- Complexity Measures for Public-Key Cryptosystems
- Computational Complexity of Probabilistic Turing Machines
- Defying upward and downward separation
- Easily Checked Generalized Self-Reducibility
- Generic oracles, uniform machines, and codes
- scientific article; zbMATH DE number 3988707 (Why is no real title available?)
- scientific article; zbMATH DE number 4033067 (Why is no real title available?)
- scientific article; zbMATH DE number 18632 (Why is no real title available?)
- scientific article; zbMATH DE number 58312 (Why is no real title available?)
- scientific article; zbMATH DE number 559220 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Immunity, Relativizations, and Nondeterminism
- IP = PSPACE
- Near-Testable Sets
- Notions of weak genericity
- On closure properties of bounded two-sided error complexity classes
- On the construction of parallel computers from various basis of Boolean functions
- On the random oracle hypothesis
- Random languages for nonuniform complexity classes
- Random oracles separate PSPACE from 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
- Relativizations of Unambiguous and Random Polynomial Time Classes
- Simplicity, immunity, relativizations and nondeterminism
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- The Boolean Hierarchy I: Structural Properties
- The Boolean Hierarchy II: Applications
- The generic oracle hypothesis is false
- The random oracle hypothesis is false
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
Cited in
(10)- P-immune sets with holes lack self-reducibility properties.
- A second step towards complexity-theoretic analogs of Rice's Theorem
- A new algorithm design technique for hard problems
- Resource bounded immunity and simplicity
- scientific article; zbMATH DE number 1665448 (Why is no real title available?)
- The Power of Self-Reducibility: Selectivity, Information, and Approximation
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting
- A result relating disjunctive self-reducibility to P-immunity
- Bi-immunity results for cheatable sets
This page was built for publication: Strong self-reducibility precludes strong immunity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4895818)
