Mundos relativos a los que no existen "generadores invulnerables"

Los generadores invulnerables se definen de la siguiente manera:

Sea una relación NP y M una máquina que acepte L ( R ) . Informalmente, un programa es un generador invulnerable si, en la entrada 1 n , produce pares de instancia-testigo ( x , w ) ∈ R , con | x | = n , de acuerdo con una distribución bajo la cual cualquier adversario en tiempo polinómico al que se le da x no encuentra un testigo de que x ∈ S , con probabilidad notable, para infinitas longitudes n .$R$$M$$L(R)$$1^n$$(x, w) \in R$$|x| = n$$x$$x \in S$$n$

Generadores invulnerables, definidos por primera vez por Abadi et al. , encontré muchas aplicaciones en criptografía.

La existencia de los generadores invulnerables se basa en el supuesto de que , aunque esto posiblemente no sea suficiente (ver también el tema relacionado ).$\mathbf{P} \neq \mathbf{NP}$

El teorema 3 de Abadi et al. El documento, citado anteriormente, muestra que cualquier prueba de la existencia de generadores invulnerables no relativiza:

Teorema 3. Existe un oráculo tal que P B ≠ N P B , y los generadores invulnerables no existen en relación con B.$B$$\mathbf{P}^B \neq \mathbf{NP}^B$

No entiendo una parte de la prueba de este teorema. Deje denotar la operación de unión disjunta . Sea Q B F el lenguaje completo de PSPACE de fórmulas booleanas cuantificadas satisfactorias, y sea K un conjunto extremadamente escaso de cadenas de máxima complejidad de Kolmogorov. Específicamente, K contiene una cadena de cada longitud n i , donde la secuencia n 1 , n 2 , ... se define por: n 1 = 2 , n i es triplemente exponencial en $\sqcup$$QBF$$K$$K$$n_i$$n_1, n_2, \ldots$$n_1 = 2$$n_i$ , parai>1; six∈Ky | x | =n, entoncesxtiene la complejidad de Kolmogorovn.$n_{i-1}$$i > 1$$x \in K$$|x| = n$$x$$n$

Los estados de papel que en relación con , se cumple que P ≠ N P . ¿Puedes explicar? (Además, aclare si B es recursivo).$B = QBF \sqcup K$$\mathbf{P} \neq \mathbf{NP}$$B$

$K$$K$$x \in K$$n$$x$$K(x) = n$$K(n) \leq \log n$$B$

$U$$K_U[f(n), g(n)]$$x$$d$$|d| \leq f(|x|)$$x = U(d)$$U(d)$$g(|x|)$$P \neq NP$

$tow_3(1)=2$$tow_3(n+1)=2^{2^{2^{n}}}$$C$$C \subseteq \{1^{tow_3(n)} : n \geq 1\}$$C \in TIME[n^{\log n}] - P$$tow_3(n)$$K[\log n, n^{\log n}] - K[\log n, n^{\log \log n}]$$K$$1^{tow_3(n)} \in C$$C = \{1^n : (\exists x)[|x|=n \text{ and } x \in K]\}$$C \in NP^{K}$

$C \notin P^{K}$$P^K \neq NP^K$$C \in P^{K}$$M$$C = L(M^K)$$C \in P$$C$$x = 1^{tow_3(n_0)}$

1. $K$$|x|$$\log \log \log |x|$$U(d)$$d$$|x|$

2. $M(x)$$M(x)$$|x|$

$y \in K$$M^K$ $y$$y$$y \in K[\log n, n^k]$$n^k$$M$$y$ $K[\log n, n^{\log \log n}]$