SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle
Rahul Ilango · SIAM Journal on Computing · 2023
Abstract. 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.