10
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very detailed and well written. Thanks Joshua! $\endgroup$ – M.S. Dousti Sep 26 '10 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.