On the (non) NP-hardness of computing circuit complexity

DOI10.4086/TOC.2017.V013A004MaRDI QIDQ5368903zbMATH OpenOpenAlexFDO

Authors Cody D. Murray, Ryan Williams

Publication date 11 October 2017

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2017.v013a004

zbMATH Keywords

circuit lower boundsminimum circuit size problemNP-completenessprojectionsreductions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the (non) NP-hardness of computing circuit complexity
• On the NP-Completeness of the Minimum Circuit Size Problem.
• Limits of minimum circuit size problem as oracle
• The non-hardness of approximating circuit size
• The non-hardness of approximating circuit size

Cited in

(41)

• On solving hard problems by polynomial-size circuits
• Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
• Hardness of sparse sets and minimal circuit size problem
• Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
• The minimum oracle circuit size problem
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• Minimum circuit size, graph isomorphism, and related problems
• Circuit minimization problem
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• On Circuit-Size Complexity and the Low Hierarchy in NP
• scientific article; zbMATH DE number 4090800 (Why is no real title available?)
• Circuit Definitions of Nondeterministic Complexity Classes
• New Collapse Consequences of NP Having Small Circuits
• scientific article; zbMATH DE number 1222577 (Why is no real title available?)
• On the (non) NP-hardness of computing circuit complexity
• On the complexity of gradient gate circuits
• Minimum circuit size, graph isomorphism, and related problems
• Circuit lower bounds for MCSP from local pseudorandom generators
• Circuit lower bounds for MCSP from local pseudorandom generators
• \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• scientific article; zbMATH DE number 7561759 (Why is no real title available?)
• On Non-Detectability of Non-Computability and the Degree of Non-Computability of Solutions of Circuit and Wave Equations on Digital Computers
• On the average-case complexity of MCSP and its variants
• scientific article; zbMATH DE number 7204388 (Why is no real title available?)
• scientific article; zbMATH DE number 7250145 (Why is no real title available?)
• New insights on the (non-)hardness of circuit minimization and related problems
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
• Limits of minimum circuit size problem as oracle
• The non-hardness of approximating circuit size
• The non-hardness of approximating circuit size
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• MCSP is hard for read-once nondeterministic branching programs
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Gap MCSP is not (Levin) NP-complete in obfustopia
• Minimum synthesis cost of CNOT circuits
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Towards a library for straight-line programs
• SAT reduces to the minimum circuit size problem with a random oracle
• Hardness hypotheses, derandomization, and circuit complexity

This page was built for publication: On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity

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