scientific article; zbMATH DE number 522855

MaRDI QIDQ4284249zbMATH OpenFDO

Authors Lane A. Hemaspaandra, Riccardo Silvestri

Publication date 24 March 1994

zbMATH Keywords

Kolmogorov complexityNPself-reducibilitysparse languageskernel constructibilitycommittability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Easily Checked Generalized Self-Reducibility
• Padding, commitment and self-reducibility
• scientific article; zbMATH DE number 4096780
• Self-reducible sets of small density
• scientific article; zbMATH DE number 4179363

Cited in

(2)

• scientific article; zbMATH DE number 3845080 (Why is no real title available?)
• Easily Checked Generalized Self-Reducibility

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 Q4284249)