Limits of minimum circuit size problem as oracle

DOI10.4230/LIPICS.CCC.2016.18zbMATH Open1380.68240MaRDI QIDQ5368752FDOQ5368752

Authors Shuichi Hirahara, Osamu Watanabe 

Publication date 10 October 2017

zbMATH Keywords

NP-completenessminimum circuit size problemTuring reductionsrandomized reductionsresource-bounded Kolmogorov complexity

Mathematics Subject Classification ID

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

Recommendations

• The minimum oracle circuit size problem
• The Minimum Oracle Circuit Size Problem.
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• On the (non) NP-hardness of computing circuit complexity
• The non-hardness of approximating circuit size

Cited in

(27)

• The power of natural properties as oracles
• scientific article; zbMATH DE number 7561559 (Why is no real title available?)
• The non-hardness of approximating circuit size
• The non-hardness of approximating circuit size
• Circuit size relative to pseudorandom oracles
• scientific article; zbMATH DE number 7250147 (Why is no real title available?)
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• scientific article; zbMATH DE number 7204388 (Why is no real title available?)
• scientific article; zbMATH DE number 7250145 (Why is no real title available?)
• One-tape Turing machine and branching program lower bounds for MCSP
• On nonadaptive reductions to the set of random strings and its dense subsets
• The final nail in the coffin of statistically-secure obfuscator
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• Circuit lower bounds from NP-hardness of MCSP under turing reductions
• The Minimum Oracle Circuit Size Problem.
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• The Complexity of Complexity
• Hardness of sparse sets and minimal circuit size problem
• The minimum oracle circuit size problem
• Discrete logarithm and minimum circuit size
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• Minimum circuit size, graph isomorphism, and related problems
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• On the (non) NP-hardness of computing circuit complexity
• Minimum circuit size, graph isomorphism, and related problems
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)

This page was built for publication: Limits of minimum circuit size problem as oracle

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