Nonuniform lower bounds for exponential time classes

DOI10.1007/3-540-60246-1_122zbMATH Open1188.68145OpenAlexW1815441906MaRDI QIDQ3569008FDOQ3569008

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

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

Mathematics Subject Classification ID

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

Cited In (7)

• New non-uniform lower bounds for uniform classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds against weakly-uniform threshold circuits
• Unconditional Lower Bounds against Advice
• Languages to diagonalize against advice classes
• Nonuniform complexity classes specified by lower and upper bounds

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)