Volume 19 (2023) Article 4 pp. 1-61
CCC 2020 Special Issue

Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions

by Shuichi Hirahara

Received: August 18, 2020
Revised: September 26, 2022
Published: October 14, 2023

$\newcommand{\SAT}{\mathsf{SAT}}$ $\newcommand{\PH}{\mathsf{PH}}$ $\newcommand{\NP}{\mathsf{NP}}$ $\newcommand{\Kt}{\mathsf{Kt}}$

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.

DOI: 10.4086/toc.2023.v019a004

© 2023 Shuichi Hirahara
Licensed under a Creative Commons Attribution License (CC-BY)