A relativization perspective on meta-complexity

DOI10.4230/LIPICS.STACS.2022.54MaRDI QIDQ6491000zbMATH OpenFDO

Authors Hanlin Ren, Rahul Santhanam

Publication date 23 April 2024

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2022.54

zbMATH Keywords

meta-complexityminimum circuit size problemrelativization

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(3)

• Gap MCSP is not (Levin) NP-complete in obfustopia
• Lower bounds for Levin-Kolmogorov complexity
• SAT reduces to the minimum circuit size problem with a random oracle

This page was built for publication: A relativization perspective on meta-complexity

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