The non-hardness of approximating circuit size

DOI10.1007/978-3-030-19955-5_2OpenAlexW2902479036MaRDI QIDQ5919681

Eric W. Allender, Rahul Ilango, Neekon Vafa

Publication date: 22 October 2019

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1721.1/133146.2

zbMATH Keywords

NP-completenessreductionstime-bounded Kolmogorov complexityMinimum Circuit Size problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size

This page was built for publication: The non-hardness of approximating circuit size