On the (non) NP-hardness of computing circuit complexity
DOI10.4086/TOC.2017.V013A004zbMATH Open1378.68053OpenAlexW2787265165MaRDI QIDQ5368903FDOQ5368903
Authors: Cody D. Murray, Ryan Williams 
Publication date: 11 October 2017
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2017.v013a004
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (34)
- On the (non) NP-hardness of computing circuit complexity
- On Non-Detectability of Non-Computability and the Degree of Non-Computability of Solutions of Circuit and Wave Equations on Digital Computers
- Title not available (Why is that?)
- On solving hard problems by polynomial-size circuits
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- New Collapse Consequences of NP Having Small Circuits
- The minimum oracle circuit size problem
- Title not available (Why is that?)
- Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
- Circuit Definitions of Nondeterministic Complexity Classes
- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
- Circuit minimization problem
- Hardness of sparse sets and minimal circuit size problem
- MCSP is hard for read-once nondeterministic branching programs
- Title not available (Why is that?)
- Circuit lower bounds for MCSP from local pseudorandom generators
- Circuit lower bounds for MCSP from local pseudorandom generators
- On the complexity of gradient gate circuits
- On Circuit-Size Complexity and the Low Hierarchy in NP
- On the average-case complexity of MCSP and its variants
- New insights on the (non-)hardness of circuit minimization and related problems
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- The non-hardness of approximating circuit size
- The non-hardness of approximating circuit size
- NP-hardness of approximating meta-complexity: a cryptographic approach
- Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
- Title not available (Why is that?)
- Hardness hypotheses, derandomization, and circuit complexity
- Cryptographic hardness under projections for time-bounded Kolmogorov complexity
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- Minimum circuit size, graph isomorphism, and related problems
- Minimum circuit size, graph isomorphism, and related problems
- Title not available (Why is that?)
- Limits of minimum circuit size problem as oracle
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)
