Bi-immune sets for complexity classes

DOI10.1007/BF01699457zbMath0572.68035OpenAlexW1981282181MaRDI QIDQ3690222

José L. Balcázar, Uwe Schoening

Publication date: 1985

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01699457

zbMATH Keywords

densitysplittingapproximation algorithmsEXPTIMEimmune setsalmost everywhere complexity

Mathematics Subject Classification ID

Related Items (42)

Bi-immunity separates strong NP-completeness notions ⋮ On solving hard problems by polynomial-size circuits ⋮ Almost every set in exponential time is P-bi-immune ⋮ A comparison of polynomial time completeness notions ⋮ Genericity and measure for exponential time ⋮ A classification of complexity core lattices ⋮ On simple and creative sets in NP ⋮ Index sets and presentations of complexity classes ⋮ The structure of generalized complexity cores ⋮ A note on separating the relativized polynomial time hierarchy by immune sets ⋮ A new algorithm design technique for hard problems ⋮ Autoreducibility, mitoticity, and immunity ⋮ E-complete sets do not have optimal polynomial time approximations ⋮ A note on balanced immunity ⋮ Sets computable in polynomial time on average ⋮ Honest polynomial time reducibilities and the \(P=?NP\) problem ⋮ OnP-subset structures ⋮ A result relating disjunctive self-reducibility to P-immunity ⋮ Kolmogorov complexity and degrees of tally sets ⋮ Recursion-theoretic ranking and compression ⋮ Bi-immunity results for cheatable sets ⋮ Immunity and pseudorandomness of context-free languages ⋮ Strong self-reducibility precludes strong immunity ⋮ Weak completeness in \(\text{E}\) and \(\text{E}_{2}\) ⋮ On optimal polynomial time approximations: P-levelability vs. δ-levelability ⋮ Relativized isomorphisms of NP-complete sets ⋮ If not empty, NP-P is topologically large ⋮ Unnamed Item ⋮ Partial bi-immunity, scaled dimension, and NP-completeness ⋮ Almost-everywhere complexity hierarchies for nondeterministic time ⋮ Exponential-time and subexponential-time sets ⋮ A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes ⋮ Low sets without subsets of higher many-one degree ⋮ Some consequences of the existnce of pseudorandom generators ⋮ Almost every set in exponential time is P-bi-immune ⋮ Genericity and measure for exponential time ⋮ On inefficient special cases of NP-complete problems ⋮ Complete sets and closeness to complexity classes ⋮ Complete distributional problems, hard languages, and resource-bounded measure ⋮ Sets without subsets of higher many-one degree ⋮ Resource bounded immunity and simplicity ⋮ Degrees of sets having no subsets of higher m- and t t-degree

Cites Work

• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• A comparison of polynomial time reducibilities
• On splitting recursive sets
• Relativizations comparing NP and exponential time
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Completeness, Approximation and Density
• On Reducibility to Complex or Sparse Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Bi-immune sets for complexity classes