Nonuniform lower bounds for exponential time classes

DOI10.1007/3-540-60246-1_122MaRDI QIDQ3569008zbMATH OpenOpenAlexFDO

Authors S. Homer, Sarah E. Mocas

Publication date 17 June 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60246-1_122

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) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Unconditional Lower Bounds against Advice
• New non-uniform lower bounds for uniform classes
• Symmetry of Information and Nonuniform Lower Bounds
• Time-space tradeoffs for SAT on nonuniform machines
• Lowness Properties of Sets in the Exponential-Time Hierarchy

Cited in

(7)

• Unconditional Lower Bounds against Advice
• scientific article; zbMATH DE number 1759402 (Why is no real title available?)
• Nonuniform complexity classes specified by lower and upper bounds
• Lower bounds against weakly-uniform threshold circuits
• scientific article; zbMATH DE number 1405686 (Why is no real title available?)
• New non-uniform lower bounds for uniform classes
• Languages to diagonalize against advice classes

This page was built for publication: Nonuniform lower bounds for exponential time classes

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