Languages to diagonalize against advice classes

DOI10.1007/S00037-005-0202-1zbMATH Open1105.68044OpenAlexW1991680843MaRDI QIDQ853646FDOQ853646

Authors: Chris Pollett 

Publication date: 17 November 2006

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-005-0202-1

Recommendations

• New non-uniform lower bounds for uniform classes
• Nonuniform lower bounds for exponential time classes
• Unconditional Lower Bounds against Advice
• scientific article; zbMATH DE number 1318518
• A Note on polynomial-size circuits with low resource-bounded Kolmogorov complexity

zbMATH Keywords

complexity classesAdvice classesnonuniform computationp-selective

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (1)

• Lower bounds against weakly-uniform threshold circuits

This page was built for publication: Languages to diagonalize against advice classes

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