Languages to diagonalize against advice classes

DOI10.1007/S00037-005-0202-1MaRDI QIDQ853646zbMATH OpenOpenAlexFDO

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

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)

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

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)