Worlds Relative to Which "Invulnerable Generators" Do Not Exist

Question

Invulnerable generators are defined as follows:

Let $R$ be an NP relation, and $M$ be a machine which accepts $L(R)$. Informally, a program is an invulnerable generator if, on input $1^n$, it produces instance-witness pairs $(x, w) \in R$, with $|x| = n$, according to a distribution under which any polynomial-time adversary who is given $x$ fails to find a witness that $x \in S$, with noticeable probability, for infinitely many lengths $n$.

Invulnerable generators, first defined by Abadi et al., found many applications in cryptography.

Existence of the invulnerable generators is based on the assumption that $\mathbf{P} \neq \mathbf{NP}$, yet this is possibly not sufficient (see also the related topic).

Theorem 3 of Abadi et al. paper, cited above, shows that any proof of the existence of invulnerable generators does not relativize:

Theorem 3. There is an oracle $B$ such that $\mathbf{P}^B \neq \mathbf{NP}^B$, and invulnerable generators do not exist relative to B.

I don't understand a part of the proof of this theorem. Let $\sqcup$ denote the disjoint union operation. Let $QBF$ be the PSPACE-complete language of satisfiable quantified Boolean formulas, and let $K$ be an extremely sparse set of strings of maximum Kolmogorov complexity. Specifically, $K$ contains one string of each length $n_i$, where the sequence $n_1, n_2, \ldots$ is defined by: $n_1 = 2$, $n_i$ is triply exponential in $n_{i-1}$, for $i > 1$; if $x \in K$ and $|x| = n$, then $x$ has Kolmogorov complexity $n$.

The paper states that relative to $B = QBF \sqcup K$, it holds that $\mathbf{P} \neq \mathbf{NP}$. Can you explain? (Also, please clarify whether $B$ is recursive.)

Answer 1

If they were simply talking about (non-resource-bounded) Kolmogorov complexity, then $K$ would be uncomputable (otherwise you could use a machine computing $K$ to give short descriptions of the strings $x \in K$, since all you need to do is describe the machine and the length $n$ of $x$, and we have $K(x) = n$ yet $K(n) \leq \log n$), hence $B$ would be uncomputable as well.

However, the paper Abadi et al. reference (Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. FOCS 1983.) uses a resource-bounded version Kolmogorov complexity. Let $U$ be an efficient universal Turing machine. Define $K_U[f(n), g(n)]$ to be the sets of strings $x$ such that there is a string $d$ of length $|d| \leq f(|x|)$ such that $x = U(d)$ and the computation of $U(d)$ takes at most $g(|x|)$ time. At the top of the second column on p. 444 of that paper, Hartmanis describes how to use this concept to construct a (computable) oracle relative to which $P \neq NP$.

Here is Hartmanis' idea, adapted to the Abadi et al. result. Let $tow_3(1)=2$ and $tow_3(n+1)=2^{2^{2^{n}}}$ (which I believe is the function you described). By standard diagonalization (e.g. as in the time hierarchy theorem), construct a tally set $C$ such that $C \subseteq \{1^{tow_3(n)} : n \geq 1\}$ and $C \in TIME[n^{\log n}] - P$. Now place the first string of length $tow_3(n)$ from $K[\log n, n^{\log n}] - K[\log n, n^{\log \log n}]$ into $K$ iff $1^{tow_3(n)} \in C$. Since $C = \{1^n : (\exists x)[|x|=n \text{ and } x \in K]\}$, we have $C \in NP^{K}$.

We also have $C \notin P^{K}$, hence $P^K \neq NP^K$. Suppose for the sake of contradiction that $C \in P^{K}$. Then there is a poly-time oracle machine $M$ such that $C = L(M^K)$. I claim that this implies $C \in P$ (without the oracle!), contradicting the construction of $C$. Here's the poly-time algorithm: on input $x = 1^{tow_3(n_0)}$:

1. Compute all strings in $K$ of length strictly less than $|x|$. This can be done in polynomial time because all such strings have length at most $\log \log \log |x|$, and we just need to test the computation of $U(d)$ on even smaller strings $d$, for amounts of time that are still very small compared to $|x|$.

2. Run $M(x)$, simulating oracle queries to smaller strings with the results of (1). If $M(x)$ ever queries a string of length $|x|$, simulate that query with a "NO" answer.

The reason step (2) works it that, for sufficiently large input lengths, if there is a string $y \in K$ of that length, $M^K$ cannot query $y$, so we can simulate all such queries with a NO answer. If it did query $y$, then we would have $y \in K[\log n, n^k]$ (where $n^k$ bounds the run-time of $M$), contradicting the fact that we chose $y$ to be not in $K[\log n, n^{\log \log n}]$.