# Worlds Relative to Which "Invulnerable Generators" Do Not Exist

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.)

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}]$.

• Very detailed and well written. Thanks Joshua! Sep 26, 2010 at 2:49