New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems

DOI10.1145/3349616zbMath1441.68081OpenAlexW2773570193WikidataQ127240068 ScholiaQ127240068MaRDI QIDQ5205823

Shuichi Hirahara, Eric W. Allender

Publication date: 16 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3349616

zbMATH Keywords

computational complexityKolmogorov complexitycircuit sizeMCSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (7)

Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization

This page was built for publication: New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems