scientific article; zbMATH DE number 4179363

MaRDI QIDQ3203013zbMATH OpenFDO

Authors Klaus Ambos-Spies, Jürgen Kämper

Publication date 1989

zbMATH Keywords

NP setsdisjunctive self-reducibilityexistence of sparse sets in NP-Pself-proving

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Natural Self-Reducible Sets
• Self-reducible sets of small density
• A result relating disjunctive self-reducibility to P-immunity
• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• CONJUNCTIVE AND DISJUNCTIVE REDUCIBILITIES TO SPARSE AND TALLY SETS REVISITED

Cited in

(6)

• P-immune sets with holes lack self-reducibility properties.
• A result relating disjunctive self-reducibility to P-immunity
• scientific article; zbMATH DE number 20700 (Why is no real title available?)
• Self-reducible sets of small density
• Natural Self-Reducible Sets
• scientific article; zbMATH DE number 522855 (Why is no real title available?)

This page was built for publication:

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