scientific article; zbMATH DE number 6789283
From MaRDI portal
Publication:5368752
DOI10.4230/LIPIcs.CCC.2016.18zbMath1380.68240MaRDI QIDQ5368752
Shuichi Hirahara, Osamu Watanabe
Publication date: 10 October 2017
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
NP-completenessminimum circuit size problemTuring reductionsrandomized reductionsresource-bounded Kolmogorov complexity
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (19)
Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Discrete logarithm and minimum circuit size ⋮ 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 ⋮ Unnamed Item ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ Hardness of sparse sets and minimal circuit size problem ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions
This page was built for publication:
