Resource bounds and subproblem independence

DOI10.1007/S00224-004-1160-8MaRDI QIDQ2581008zbMATH OpenOpenAlexFDO

Authors R. E. Stearns, H. B. III Hunt

Publication date 10 January 2006

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-004-1160-8

zbMATH Keywords

\(q\)-linear functions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Resource bounded randomness and weakly complete problems
• scientific article; zbMATH DE number 1555954
• On the complexity of approximating the independent set problem
• A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem
• On resource-bounded instance complexity
• Parameterized extension complexity of independent set and related problems
• Resource-bounded instance complexity
• Strong polynomiality of resource constraint propagation
• On the complexity of approximating the independent set problem (extended abstract)
• Resource-bounded Kolmogorov complexity revisited

This page was built for publication: Resource bounds and subproblem independence

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