Unexpected hardness results for Kolmogorov complexity under uniform reductions

Hardness of computing the Kolmogorov complexity of a given string is closely tied to a security proof of hitting set generators, and thus understanding hardness of Kolmogorov complexity is one of the central questions in complexity theory. In this paper, we develop new proof techniques to show hardness of computing Kolmogorov complexity under surprisingly efficient reductions, which were previously conjectured to be impossible. It is known that the set R K of Kolmogorov-random strings is PSPACE-hard under polynomial-time Turing reductions, i.e., PSPACE ⊆ P RK , and that NEXP ⊆ NP RK , which was conjectured to be tight by Allender [All12]. We prove that EXP NP ⊆ P RK , which simultaneously improves these hardness results and refutes the conjecture of Allender under the plausible assumption that EXP NP = NEXP. At the core of our results is a new security proof of a pseudorandom generator via a black-box uniform reduction, which overcomes an impossibility result of Gutfreund and Vadhan [GV08].

Our proof techniques have further consequences, including:

1. Applying our proof techniques to the case of resource-bounded Kolmogorov complexity, we obtain NP-hardness of the problem MINcKT SAT of computing conditional polynomialtime-bounded SAT-oracle Kolmogorov complexity under polynomial-time deterministic reductions. In contrast, the Minimum SAT-Oracle Circuit Size Problem cannot be NP-hard under polynomial-time deterministic reductions without resolving EXP = ZPP. Our hardness result is the first result that overcomes the non-NP-hardness results of MCSP. We also prove DistNP-hardness of MINKT SAT , which is a partial converse of the approach of Hirahara [Hir18] for proving the equivalence between worst-case and average-case complexity of NP.

2. We prove S p 2 -hardness of Kolmogorov complexity under quasi-polynomial-time nonadaptive reductions. This is the first result that overcomes a P/poly barrier result of Allender, Buhrman, Friedman, and Loff [ABFL14].

We also establish a firm link between non-trivial satisfiability algorithms and the immunity of random strings, and we obtain the following unconditional lower bounds.

Kolmogorov-random strings is decidable in P. We resolve this open question, by showing that the set of super-polynomial-time-bounded Kolmogorov-random strings is P-immune, which is a much stronger lower bound than an average-case lower bound.

2. The set of Levin's Kolmogorov-random strings is (P-uniform ACC 0 )-immune.