SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle
SIAM Journal on Computing · 30.06.2026 · 55 (3) · FOCS23-309-FOCS23-359
DOI: 10.1137/24m1652568 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 09.06.2026. Verfasst von Rahul Ilango. Die Arbeit nennt 92 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
The minimum circuit size problem ([Formula: see text]) asks, given the truth table of a Boolean function [Formula: see text] and an integer [Formula: see text], if there is a circuit computing [Formula: see text] of size at most [Formula: see text]. It is a long-standing open question whether [Formula: see text] is [Formula: see text]-complete. We give, in our view, the strongest evidence yet that [Formula: see text] is in fact [Formula: see text]-complete. Specifically, we show that, with probability one, there is a [Formula: see text] reduction from the [Formula: see text]-hard problem of approximating vertex cover on hypergraphs to [Formula: see text] on circuits that have access to a uniformly random oracle [Formula: see text] (the reduction can be made uniform if it is given access to [Formula: see text]). Our reduction yields near-optimal additive hardness of approximation and extends to computing time-bounded Kolmogorov complexity ([Formula: see text]). Heuristically “instantiating” [Formula: see text] with real-world cryptographic hash functions, we get a plethora of candidate uniform deterministic polynomial-time many-one reductions from [Formula: see text] to [Formula: see text] and [Formula: see text] in the standard unrelativized world. To our knowledge, no candidate reduction from [Formula: see text] to [Formula: see text] or [Formula: see text] was known previously. Moreover, our results hold in the regime where [Formula: see text] has a non–black-box worst-case to average-case reduction [Hirahara, Non-black-box worst-case to average-case reductions within NP, 2018]. Thus, intriguingly, the existence of sufficiently “unstructured” functions implies that a problem with a known (non–black-box) worst-case to average-case reduction is [Formula: see text]-complete.
Förderung
- National Science Foundation
Zitieren
APA
Ilango, R. (2026). SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle. SIAM Journal on Computing, 55(3), FOCS23-309-FOCS23-359. https://doi.org/10.1137/24m1652568
Vancouver
Ilango R. SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle. SIAM Journal on Computing. 2026;55(3):FOCS23-309-FOCS23-359. doi:10.1137/24m1652568
BibTeX
@article{Ilango2026,
author = {Ilango, Rahul},
title = {SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {3},
pages = {FOCS23--309--FOCS23--359},
doi = {10.1137/24m1652568}
}
EUVIMED