Bi-immune sets for complexity classes
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3443638 (Why is no real title available?)
- A comparison of polynomial time reducibilities
- Completeness, Approximation and Density
- 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
(57)- Immunity for closed sets
- On simple and creative sets in NP
- Bi-immunity separates strong NP-completeness notions
- Honest polynomial time reducibilities and the \(P=?NP\) problem
- Set-theoretic structure of computable sets
- A parameterized halting problem, _0 truth and the MRDP theorem
- On solving hard problems by polynomial-size circuits
- A classification of complexity core lattices
- E-complete sets do not have optimal polynomial time approximations
- The structure of generalized complexity cores
- Almost every set in exponential time is P-bi-immune
- A comparison of polynomial time completeness notions
- On the unavoidability of primitive words and other languages
- Effective bi-immunity and randomness
- Resource bounded immunity and simplicity
- A note on separating the relativized polynomial time hierarchy by immune sets
- Low sets without subsets of higher many-one degree
- Bi-immunity over different size alphabets
- Immunity of complete problems
- Immunity and simplicity in relativizations of probabilistic complexity classes
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Immunity, Relativizations, and Nondeterminism
- Autoreducibility, mitoticity, and immunity
- On optimal polynomial time approximations: p-levelability vs. -levelability
- Exponential-time and subexponential-time sets
- A note on balanced immunity
- Partial bi-immunity, scaled dimension, and NP-completeness
- Almost every set in exponential time is P-bi-immune
- Complete distributional problems, hard languages, and resource-bounded measure
- On Some Complexity Characteristics of Immune Sets
- Complete sets and closeness to complexity classes
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- Some consequences of the existnce of pseudorandom generators
- Immunity and pseudorandomness of context-free languages
- Sets computable in polynomial time on average
- A new algorithm design technique for hard problems
- Sets without subsets of higher many-one degree
- Index sets and presentations of complexity classes
- From bi-immunity to absolute undecidability
- 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
- Almost-everywhere complexity hierarchies for nondeterministic time
- Degrees of sets having no subsets of higher m- and t t-degree
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- OnP-subset structures
- Strong self-reducibility precludes strong immunity
- On inefficient special cases of NP-complete problems
- Genericity and measure for exponential time
- scientific article; zbMATH DE number 88937 (Why is no real title available?)
- Recursion-theoretic ranking and compression
- scientific article; zbMATH DE number 2086403 (Why is no real title available?)
- Genericity and measure for exponential time (extended abstract)
- scientific article; zbMATH DE number 1962844 (Why is no real title available?)
- If not empty, NP-P is topologically large
- Relativized isomorphisms of NP-complete sets
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)
