Resource-bounded instance complexity

DOI10.1007/3-540-59042-0_108MaRDI QIDQ4596656zbMATH OpenOpenAlexFDO

Authors Lance Fortnow, Martin Kummer

Publication date 4 December 2017

Published in STACS 95 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59042-0_108

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• On resource-bounded instance complexity
• scientific article; zbMATH DE number 1361500
• On hard instances
• scientific article; zbMATH DE number 1500526
• Instance complexity

Cited in

(4)

• On resource-bounded instance complexity
• Resource bounds and subproblem independence
• Instance complexity
• scientific article; zbMATH DE number 1361500 (Why is no real title available?)

This page was built for publication: Resource-bounded instance complexity

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