Welten, auf denen es keine „unverwundbaren Generatoren“ gibt

Unverwundbare Generatoren sind wie folgt definiert:

Sei eine NP-Beziehung und eine Maschine, die akzeptiert . Informell ist ein Programm ein unverwundbarer Generator, wenn es bei Eingabe Instanz-Zeugen-Paare mit , gemäß einer Verteilung, unter der jeder Gegner mit Polynomzeit, dem gegeben wird , keinen Zeugen findet, dass mit erkennbarer Wahrscheinlichkeit für unendlich viele Längen .$R$$M$$L(R)$$1^n$$(x, w) \in R$$|x| = n$$x$$x \in S$$n$

Unverwundbare Generatoren, zuerst definiert von Abadi et al. fand viele Anwendungen in der Kryptographie.

Die Existenz der unverwundbaren Generatoren basiert auf der Annahme, dass , dies ist jedoch möglicherweise nicht ausreichend (siehe auch das verwandte Thema ).$\mathbf{P} \neq \mathbf{NP}$

Satz 3 von Abadi et al. Das oben zitierte Papier zeigt, dass ein Beweis für die Existenz unverwundbarer Generatoren nicht relativiert:

Satz 3. Es gibt ein Orakel so dass und unverwundbare Generatoren relativ zu B nicht existieren.$B$$\mathbf{P}^B \neq \mathbf{NP}^B$

Ich verstehe keinen Teil des Beweises dieses Satzes. Lassen bezeichnen die disjunkte Vereinigung Betrieb. Sei die PSPACE-vollständige Sprache zufriedenstellbarer quantifizierter Boolescher Formeln und sei eine äußerst spärliche Menge von Strings mit maximaler Kolmogorov-Komplexität. Insbesondere enthält eine Zeichenfolge jeder Länge , wobei die Folge definiert ist durch: , ist in dreifach exponentiell , für ; wenn und , dann$\sqcup$$QBF$$K$$K$$n_i$$n_1, n_2, \ldots$$n_1 = 2$n i - 1 i > 1 x ∈ K | x | = n x $n_i$$n_{i-1}$$i > 1$$x \in K$$|x| = n$$x$hat Kolmogorov Komplexität .$n$

Die Papierzustände , die relativ zu gilt, dass . Können Sie erklären? (Bitte klären Sie auch, ob rekursiv ist.)P ≠ N P$B = QBF \sqcup K$$\mathbf{P} \neq \mathbf{NP}$$B$

Wenn sie nur über (nicht ressourcengebundene) Kolmogorov-Komplexität sprechen würden, wäre nicht berechenbar (andernfalls könnten Sie einen Maschinenrechner , um kurze Beschreibungen der Zeichenfolgen , da Sie nur beschreiben müssen die Maschine und die Länge von , und wir haben aber ), daher wäre auch nicht berechenbar.K x ∈ K N x K ( x ) = n K ( n ) ≤ log n $K$$K$$x \in K$$n$$x$$K(x) = n$$K(n) \leq \log n$$B$

Das Papier Abadi et al. Die Referenz ( Hartmanis. Verallgemeinerte Kolmogorov-Komplexität und die Struktur realisierbarer Berechnungen. FOCS 1983. ) verwendet eine ressourcengebundene Version der Kolmogorov-Komplexität. Sei eine effiziente universelle Turingmaschine. Definieren Sie als die Mengen von Zeichenfolgen so dass es eine Zeichenfolge der Länge so dass und die Berechnung von höchstens Zeit benötigt. Oben in der zweiten Spalte auf S. In 444 dieses Papiers beschreibt Hartmanis, wie man dieses Konzept verwendet, um ein (berechenbares) Orakel zu konstruieren, relativ zu demK U [ f ( n ) , g ( n ) ] x d | d | ≤ f ( | x | ) x = U ( d ) U ( d ) g ( | x | ) P ≠ N $U$$K_U[f(n), g(n)]$$x$$d$$|d| \leq f(|x|)$$x = U(d)$$U(d)$$g(|x|)$$P \neq NP$.

Hier ist Hartmanis 'Idee, angepasst an Abadi et al. Ergebnis. Sei und (was meiner Meinung nach die von Ihnen beschriebene Funktion ist). Konstruieren Sie durch Standarddiagonalisierung (z. B. wie im Zeithierarchiesatz) eine Strichmenge so, dass und . Platzieren Sie nun die erste Zeichenfolge der Länge von in iff . Da , haben wir .$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}$

Wir haben auch , also . Nehmen wir im Widerspruch an, dass . Dann gibt es eine Polyzeit-Orakelmaschine so dass . Ich behaupte, dass dies impliziert (ohne das Orakel!), Was der Konstruktion von widerspricht . Hier ist der Poly-Time-Algorithmus: bei Eingabe :$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. Berechnen Sie alle Zeichenfolgen in einer Länge von weniger als. Dies kann in Polynomzeit erfolgen, da alle diese Zeichenfolgen höchstensund wir müssen nur die Berechnung von an noch kleineren Strings für Zeiträume testen, die im Vergleich zu noch sehr klein sind .$K$$|x|$$\log \log \log |x|$$U(d)$$d$$|x|$

2. Führen Sie und simulieren Sie Orakelabfragen für kleinere Zeichenfolgen mit den Ergebnissen von (1). Wenn jemals eine Zeichenfolge der Länge abfragt , simulieren Sie diese Abfrage mit einer "NEIN" -Antwort.$M(x)$$M(x)$$|x|$

Der Grundschritt (2) funktioniert so, dass bei ausreichend großen Eingabelängen, wenn es eine Zeichenfolge dieser Länge gibt, nicht abfragen kann , so dass wir alle derartigen Abfragen mit einer NEIN-Antwort simulieren können. Wenn es abfragen würde, hätten wir (wobei die Laufzeit von ), was der Tatsache widerspricht, dass wir , um nicht in .M K y y y ∈ K [ log n , n k ] n k M y K [ log n , n log log n$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}]$