<p>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.</p>

<p>However, the paper Abadi et al. reference (<a href="http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1983.21" rel="noreferrer">Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. FOCS 1983.</a>) 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$. </p>

<p>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}$. </p>

<p>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)}$:</p>

<ol>
<li><p>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|$.</p></li>
<li><p>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.</p></li>
</ol>

<p>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$ <em>cannot query $y$</em>, 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 <em>not in</em> $K[\log n, n^{\log \log n}]$.</p>

CC BY-SA 2.5
2010-09-26T02:49:58.817Z
Very detailed and well written. Thanks Joshua!
Sadeq Dousti
CC BY-SA 2.5
2010-09-25T18:05:48.213Z
2010-09-26T04:32:47.097Z
2010-09-26T04:32:47.097Z
Joshua Grochow
<p>Invulnerable generators are defined as follows:</p>
<p>Let <span class="math-container">$R$</span> be an NP relation, and <span class="math-container">$M$</span> be a machine which accepts <span class="math-container">$L(R)$</span>. Informally, a program is an <em>invulnerable generator</em> if, on input <span class="math-container">$1^n$</span>, it produces instance-witness pairs <span class="math-container">$(x, w) \in R$</span>, with <span class="math-container">$|x| = n$</span>, according to a distribution under which any polynomial-time adversary who is given <span class="math-container">$x$</span> fails to find a witness that <span class="math-container">$x \in S$</span>, with noticeable probability, for infinitely many lengths <span class="math-container">$n$</span>.</p>
<p>Invulnerable generators, first defined by <a href="https://doi.org/10.1007%2F0-387-34799-2_23?from=SL" rel="nofollow noreferrer">Abadi <em>et al.</em></a>, found many applications in cryptography.</p>
<p>Existence of the invulnerable generators is based on the assumption that <span class="math-container">$\mathbf{P} \neq \mathbf{NP}$</span>, yet this is possibly not sufficient (see also the <a href="https://cstheory.stackexchange.com/q/1026/873">related topic</a>).</p>
<p>Theorem 3 of Abadi <em>et al.</em> paper, cited above, shows that any proof of the existence of invulnerable generators does not relativize:</p>
<p><strong>Theorem 3.</strong> There is an oracle <span class="math-container">$B$</span> such that <span class="math-container">$\mathbf{P}^B \neq \mathbf{NP}^B$</span>, and invulnerable generators do not exist relative to B.</p>
<p>I don't understand a part of the proof of this theorem.
Let <span class="math-container">$\sqcup$</span> denote the <a href="https://en.wikipedia.org/wiki/Disjoint_union" rel="nofollow noreferrer">disjoint union</a> operation.
Let <span class="math-container">$QBF$</span> be the PSPACE-complete language of satisfiable quantified Boolean formulas, and let <span class="math-container">$K$</span> be an extremely sparse
set of strings of maximum Kolmogorov complexity. Specifically, <span class="math-container">$K$</span> contains one string of each length <span class="math-container">$n_i$</span>, where the sequence <span class="math-container">$n_1, n_2, \ldots$</span> is defined by: <span class="math-container">$n_1 = 2$</span>, <span class="math-container">$n_i$</span> is <strong>triply exponential</strong> in <span class="math-container">$n_{i-1}$</span>, for <span class="math-container">$i &gt; 1$</span>; if <span class="math-container">$x \in K$</span> and <span class="math-container">$|x| = n$</span>, then <span class="math-container">$x$</span> has Kolmogorov complexity <span class="math-container">$n$</span>.</p>
<blockquote>
<p>The paper states that relative to <span class="math-container">$B = QBF \sqcup K$</span>, it holds that <span class="math-container">$\mathbf{P} \neq \mathbf{NP}$</span>. Can you explain? (Also, please clarify whether <span class="math-container">$B$</span> is recursive.)</p>
</blockquote>

<cc.complexity-theory><cr.crypto-security><oracles><relativization><kolmogorov-complexity>
Worlds Relative to Which "Invulnerable Generators" Do Not Exist
Sadeq Dousti
# Worlds Relative to Which "Invulnerable Generators" Do Not Exist

(Asked by: username_0 on 2010-09-23)

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.*](https://doi.org/10.1007%2F0-387-34799-2_23?from=SL), 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](https://cstheory.stackexchange.com/q/1026/873)).

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](https://en.wikipedia.org/wiki/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.)

**Tags:** cc.complexity-theory, cr.crypto-security, oracles, relativization, kolmogorov-complexity

---

## 1 answers

### Answer by username_1 on 2010-09-25. Score: 8 | Accepted answer

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.](http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1983.21)) 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}]$.

> **Comments:**
> **username_0**: Very detailed and well written. Thanks Joshua!  

---

