Theory of Computing
-------------------
Title : Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions
Authors : Shuichi Hirahara
Volume : 19
Number : 4
Pages : 1-61
URL : https://theoryofcomputing.org/articles/v019a004
Abstract
--------
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^{SAT} vs K) 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 complexity of PH is 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 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.