On the NP-Completeness of the Minimum Circuit Size Problem.

DOI10.4230/LIPIcs.FSTTCS.2015.236zbMath1366.68074OpenAlexW2289098369MaRDI QIDQ5275370

John M. Hitchcock, A. Pavan

Publication date: 13 July 2017

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5661/pdf/47.pdf/

zbMATH Keywords

NP-completenesscircuit complexitytruth-table reductionsminimum circuit size

Mathematics Subject Classification ID

Related Items (15)

The power of natural properties as oracles ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ The final nail in the coffin of statistically-secure obfuscator ⋮ The Complexity of Complexity ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Hardness of sparse sets and minimal circuit size problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions

This page was built for publication: On the NP-Completeness of the Minimum Circuit Size Problem.