Revised: September 26, 2022

Published: October 14, 2023

**Keywords:**pseudorandom generator, hitting set generator, meta-complexity, Levin's Kt complexity, minimum circuit size problem

**Categories:**complexity theory, derandomization, pseudorandomness, hitting set, meta-complexity, Levin's Kt complexity, minimum circuit size, CCC, CCC 2020 special issue

**ACM Classification:**F.1.3

**AMS Classification:**68Q15

**Abstract:**
[Plain Text Version]

The standard notion of promise problem is a pair of *disjoint* sets of
instances, each of which is regarded as Yes and No instances, respectively,
and the task of solving a promise problem is to distinguish these two sets
of instances.
In this paper, we introduce a set of
new promise problems which are conjectured to be *non-disjoint,*
and prove that hardness of these “non-disjoint” promise problems
gives rise to
the existence of hitting set generators (and vice versa).
We do this by presenting a general principle which converts
any black-box construction of a pseudorandom generator
into the existence of a hitting set generator
whose security is based on hardness of some “non-disjoint”
promise problem (via a non-black-box security reduction).

Applying the principle to cryptographic pseudorandom generators, we introduce the Gap$(K$ vs $K^{\SAT})$ problem, which asks to distinguish strings whose time-bounded $\SAT$-oracle Kolmogorov complexity is small from strings whose time-bounded Kolmogorov complexity (without $\SAT$ oracle) is large. We show that if this problem is $\NP$-hard, the worst-case and average-case complexities of $\PH$ are equivalent. This generalizes the non-black-box worst-case to average-case reductions of Hirahara (FOCS'18) and improve the approximation error from $\widetilde{O}(\sqrt{n})$ to $O(\log n)$.

Applying the principle to complexity-theoretic pseudorandom generators, we we introduce a family of Meta-computational Circuit Lower-bound Problems (MCLPs), which are problems of distinguishing the truth tables of explicit functions from hard functions. Our results generalize the hardness versus randomness framework and identify problems whose circuit lower bounds characterize the existence of hitting set generators.

We also establish the equivalence between the existence of a non-trivial derandomization algorithm for uniform algorithms and a uniform lower bound for a problem of approximating Levin's $\Kt$-complexity.

A conference version of this paper appeared in the Proceedings of the 35th Computational Complexity Conference, CCC 2020.