Bi-immune sets for complexity classes
From MaRDI portal
Recommendations
Cites work
- A comparison of polynomial time reducibilities
- Completeness, Approximation and Density
- scientific article; zbMATH DE number 3443638 (Why is no real title available?)
- On Isomorphisms and Density of NP and Other Complete Sets
- On Reducibility to Complex or Sparse Sets
- On splitting recursive sets
- Oracle-dependent properties of the lattice of NP sets
- Recursively enumerable sets of positive integers and their decision problems
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativizations comparing NP and exponential time
Cited in
(60)- On solving hard problems by polynomial-size circuits
- A comparison of polynomial time completeness notions
- A classification of complexity core lattices
- On simple and creative sets in NP
- The structure of generalized complexity cores
- Almost-everywhere complexity hierarchies for nondeterministic time
- Exponential-time and subexponential-time sets
- Immunity of complete problems
- Almost every set in exponential time is P-bi-immune
- Genericity and measure for exponential time
- Index sets and presentations of complexity classes
- Complete distributional problems, hard languages, and resource-bounded measure
- Recursion-theoretic ranking and compression
- Some consequences of the existnce of pseudorandom generators
- On inefficient special cases of NP-complete problems
- Bi-immunity separates strong NP-completeness notions
- A new algorithm design technique for hard problems
- Bi-immunity over different size alphabets
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
- Set-theoretic structure of computable sets
- Partial bi-immunity, scaled dimension, and NP-completeness
- Sets without subsets of higher many-one degree
- Resource bounded immunity and simplicity
- Effective bi-immunity and randomness
- Low sets without subsets of higher many-one degree
- Immunity, Relativizations, and Nondeterminism
- A note on separating the relativized polynomial time hierarchy by immune sets
- Immunity for closed sets
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- OnP-subset structures
- Immunity and simplicity in relativizations of probabilistic complexity classes
- scientific article; zbMATH DE number 88937 (Why is no real title available?)
- A note on balanced immunity
- Bounded Immunity and Btt-Reductions
- scientific article; zbMATH DE number 1962844 (Why is no real title available?)
- On optimal polynomial time approximations: p-levelability vs. -levelability
- Complete sets and closeness to complexity classes
- scientific article; zbMATH DE number 2086403 (Why is no real title available?)
- On Some Complexity Characteristics of Immune Sets
- Strong self-reducibility precludes strong immunity
- On the unavoidability of primitive words and other languages
- Almost every set in exponential time is P-bi-immune
- E-complete sets do not have optimal polynomial time approximations
- Genericity and measure for exponential time (extended abstract)
- From bi-immunity to absolute undecidability
- Degrees of sets having no subsets of higher m- and t t-degree
- Sets computable in polynomial time on average
- Immunity and pseudorandomness of context-free languages
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Relativized isomorphisms of NP-complete sets
- If not empty, NP-P is topologically large
- A parameterized halting problem, _0 truth and the MRDP theorem
- Random permutations in computational complexity
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- Autoreducibility, mitoticity, and immunity
- Honest polynomial time reducibilities and the \(P=?NP\) problem
- A result relating disjunctive self-reducibility to P-immunity
- Kolmogorov complexity and degrees of tally sets
- Bi-immunity results for cheatable sets
- Counting finite subsets of an immune set
This page was built for publication: Bi-immune sets for complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3690222)
