scientific article; zbMATH DE number 1361500

MaRDI QIDQ4699319zbMATH OpenFDO

Authors Martin Mundhenk

Publication date 10 November 1999

zbMATH Keywords

decision problemhard instancesinstance complexityKolmogorov complexityNP-hardnessrecursive sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• On hard instances
• scientific article; zbMATH DE number 4001485
• Resource-bounded instance complexity
• scientific article; zbMATH DE number 1500526

Cited in

(5)

• On hard instances
• Random strings make hard instances
• scientific article; zbMATH DE number 1500526 (Why is no real title available?)
• Resource-bounded instance complexity
• scientific article; zbMATH DE number 4001485 (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 Q4699319)