Kolmogorov Complexity and derandomization

Motivation
------------

The sets $R_{\mu}$ of random strings with high Kolmogorov complexity and bounded resources are good examples of sets with a lot of information content that is difficult to access. Many of these sets have been studied [BM97,Ko91,KC00] as possible examples of intractable sets that are not complete for any of the standard complexity classes. Based on [Al05], we now show that these sets can, in fact, be exploited by efficient reductions.

The completeness results are obtained via derandomization techniques, mostly relativizing hardness vs randomness tradeoffs in the contrapositive: If there exists a problem in complexity class $C$ that is hard when given oracle access to $A$, then there exists a pseudorandom generator secure against $A$ that is computable within $C$. We argue that no pseudorandom generator computable in $C$ can be secure against $R_{\mu}$, and thus every problem in $C$ is easy given oracle access to $R_{\mu}$. In other words, $C$ reduces to $R_{\mu}$.

Definitions
-----------

The computational model that we use is the multi-tape Turing machine with random-access to its input tape (the ideas work in any general model). Wlg, we pick a single universal machine $U$.
Kolmogorov complexity $C^A(x)$ is usually defined as the length of the shortest description $d\in \{0,1\}^*$ such that $U^A(d) = x$, where $U$ is a universal Turing machine with oracle access to $A$. The definition we use is slightly different: instead of requiring $U^A(d)$ to produce $x$, it should recognize the correct value of $x_i$ for every $i$.
We now define several resource-bounded Kolmogorov complexity measures:


Definition 1 [Kt,KT,KS]
$Kt^A(x) = \min\{ |d| + \log t : U^A(d,i,b)$ accepts in $t$ steps iff $x_i=b \}$
$KT^A(x) = \min\{ |d| + t : U^A(d,i,b)$ accepts in $t$ steps iff $x_i=b \}$

The only difference is that in $KT$ the time bound is given exponentially more weight. Considering space-bounded notions, too, will yield complete problems for space-bounded
classes:

$KS^A(x) = \min\{ |d| + s : U^A(d,i,b)$ accepts in $s$ space iff $x_i=b \}$

Both $Kt$ and $KS$ can be approximated in terms of $KT^A$, for appropriate oracle choices:

Theorem 2:
There exist a complete set $A$ for $E$, a complete set $B$ for $DSPACE(n)$, and a constant $c$ s.t.
$Kt(x)/c\leq KT^A(x)$
$KS(x)/c\leq KT^B(x)$

Proof sketch: Let $A \in E$ and let $x$ be given, s.t. $KT^A(x) = m$. Thus, there is a description $d_x$ of length $\leq m$, s.t. $U^A(d_x,i,b)$ accepts iff $x_i=b$ in time at most $m$. During computation, $U$ asks queries of length at most $m$. Since $A \in E$, each query can be answered in time $2^{O(m)}$.
Let $M$ denote the algorithm simulating the computation of $U^A(d_x,i,b)$ for every $i$ by directly computing the answers of $A$, then the description $d'_x= \langle M,d_x \rangle$ is sufficient for $U$ to compute $U(d'_x,i,b)$ in time $2^{O(m)}$. As $|d'_x|=m+O(1)$, we can conclude that $Kt(x) \leq m + O(1) + \log(2^{O(m)}) = O(m)$.
The proof for $KS$ is similar.

We focus on sets containing strings of high complexity, for various measures.

Definition 3:
For any Kolmogorov complexity measure $\mu$, define
$R_{\mu} = \{x : \mu(x) \geq |x|/2\}$.

The bound of $|x|/2$ is arbitrary. Essentially, all we need is that the set $R_{\mu}$ has polynomial density (it contains at least $2^n/n^k$ strings of each length $n$, for some $k$).
The following propositions are straightforward.

Proposition 4:
$R_{Kt} \in E$, $R_{KS} \in DSPACE(n)$, and $R_{KT} \in coNP$.

Proposition 5:
The sets $R_{Kt}$, $R_{KS}$ all have polynomial density.


Nonuniform Hardness Results
-------------------------------

We show that strings of high Kolmogorov complexity are very useful as oracles. We will argue that an appropriate set $R_{\mu}$ of Kolmogorov random strings can be used to distinguish the output of a pseudorandom generator $G_f$ from truly random strings. This in turn will enable us to efficiently reduce $f$ to $R_{\mu}$.

Recall that $A$ is PSPACE-robust if $PSPACE^A = P^A$ (machines are allowed to ask oracle
queries of only polynomial size). The complete sets for many large complexity classes (PSPACE, EXP, EXPSPACE) have this property, as well as the complete sets (under linear-time
reductions) for classes like $DSPACE(n)$ and $E$.

We will build a pseudorandom generator based on the Nisan-Wigderson paradigm [NW94]. [BFNW93] construct, for any $\epsilon > 0$, a variant $G^{BFNW}_f : \{0,1\}^{n^\epsilon}\rightarrow \{0,1\}^n$ such that for any $x$ of size $n^\epsilon$, the function is computable in space $O(n^\epsilon)$ given access to the Boolean function $f$ on inputs of size at most $n^\epsilon$. If $f$ is PSPACE-robust, there is a constant $c$ independent of $\epsilon$, such that each bit is computable in time $n^{\epsilon \cdot c}$ with oracle access to $f$. The following hardness versus randomness tradeoff holds.

Theorem 6 [BFNW93]
Let $f$ be a Boolean function, $\epsilon > 0$, and $G^{BFNW}_f$ be the pseudorandom generator described above. Let $T$ be a set and $p(n)$ a polynomial. If
$|P_{r\in U_n}[r \in T]-P_{x\in U_{n^\epsilon}}[G^{BFNW}_f(x)\in T]|\geq 1/p(n)$
for all large $n$, then there exists a polynomial size oracle circuit family $\{ C_n \}$ with oracle $T$ that computes $f$ and queries $T$ non-adaptively.

We use the notation $A\leq ^{P/poly}_{tt} B$ to denote that there exists a truth-table (i.e., nonadaptive) reduction from $A$ to $B$ that is computable by a family of polynomial-size circuits.
(A truth-table reduction is a reduction from one set of natural numbers to another. Truth-table reductions are more powerful than Turing reductions in a mathematical sense, since they provide finer equivalent class, but they are a weaker tool.)

Theorem 7:
Let $A$ be any PSPACE-robust set. Let $L$ be a set of polynomial density s.t. for every $x \in L$, $KT^A(x) > |x|^\gamma$ for some constant $\gamma > 0$. Then $A$ is reducible to $L$ via $\leq^{P/poly}_{tt}$ reductions.

Proof Sketch: Let $f$ be the characteristic function of $A$. Consider $G^{BFNW}_f$,
choose $\epsilon$ as follows. We know that every bit of $G^{BFNW}_f$ is computable in time $n^{\epsilon \cdot c}$ for some constant $c$ independent of $\epsilon$, given access to $A$. Set $\epsilon= \gamma/2c$ (wlg $c > 1$).

Any string in the range of $G^{BFNW}_f$ has small $KT^A$ complexity: Let $y = G^{BFNW}_f (x)$, for some $x$. On $x$, every bit of $G^{BFNW}_f$ is computable in time $n^{\gamma/2}$ with access to oracle $A$. Hence, $KT^A(y) \leq |x|+O(n^{\gamma/2} \log n)+O(1) \leq n^{\gamma}$. Thus, $L$ distinguishes the output of $G^{BFNW}_f$ from random, and by Theorem 6, $f$ is $\leq^{P/poly}_{tt}$ reducible to $L$.

By Theorem 2 and Proposition 5, we can apply Theorem 7 to
$\langle $the set $A$ from Theorem 2, $R_{Kt}\rangle $, and $\langle $the set $B$ from Theorem 2, $R_{KS}\rangle $.
($A$ and $B$ are clearly PSPACE-robust, since they are complete for EXP and PSPACE, respectively.) Combining this with Proposition 4, we get:

Corollary 8:
$R_{Kt}$ is complete for EXP under $\leq ^{P/poly}_{tt}$ reductions. $R_{KS}$ is complete for PSPACE under $\leq ^{P/poly}_{tt}$ reductions.


Those results also obtain natural examples that witness the difference in power of various reducibilities, as some of the sets which we show are complete under truth-table reductions are provably not complete under polynomial-time many-one reductions.