A result relating disjunctive self-reducibility to P-immunity

DOI10.1016/0020-0190(90)90191-YMaRDI QIDQ915447zbMATH OpenOpenAlexFDO

Authors Jürgen Kämper

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(90)90191-y

zbMATH Keywords

self-reducibilityP-immunity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• scientific article; zbMATH DE number 4179363
• Strong self-reducibility precludes strong immunity
• scientific article; zbMATH DE number 1665448
• Immunity, Relativizations, and Nondeterminism
• \(p\)-selective self-reducible sets: a new characterization of P

Cites work

• scientific article; zbMATH DE number 4179363 (Why is no real title available?)
• scientific article; zbMATH DE number 3936519 (Why is no real title available?)
• scientific article; zbMATH DE number 4090801 (Why is no real title available?)
• scientific article; zbMATH DE number 3594673 (Why is no real title available?)
• scientific article; zbMATH DE number 817509 (Why is no real title available?)
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Bi-immune sets for complexity classes
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Immunity and simplicity in relativizations of probabilistic complexity classes
• Immunity, Relativizations, and Nondeterminism
• On helping by robust oracle machines
• On self-reducibility and weak P-selectivity
• On sparse sets in NP-P
• Oracle-dependent properties of the lattice of NP sets
• Simplicity, Relativizations and Nondeterminism
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Tally languages and complexity classes

Cited in

(4)

• P-immune sets with holes lack self-reducibility properties.
• scientific article; zbMATH DE number 4179363 (Why is no real title available?)
• scientific article; zbMATH DE number 1665448 (Why is no real title available?)
• Sets without subsets of higher many-one degree

This page was built for publication: A result relating disjunctive self-reducibility to P-immunity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q915447)