scientific article; zbMATH DE number 4179363

zbMATH Open0716.03037MaRDI QIDQ3203013FDOQ3203013

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

Publication date: 1989

Title of this publication is not available (Why is that?)

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

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)

Cited In (6)

• P-immune sets with holes lack self-reducibility properties.
• Self-reducible sets of small density
• Title not available (Why is that?)
• Natural Self-Reducible Sets
• A result relating disjunctive self-reducibility to P-immunity
• Title not available (Why is that?)

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)