Ist

8

Betrachten Sie jede Sprache . Definieren Sie s ( L ) { 0 , 1 } ω (eine unendliche Folge von Bits) durch die rekursive FormelLs(L){0,1}ω

s(L)n=χL(s(L)<n)

Hier ist die charakteristische Funktion von L, dh χ L ( w ) = 1 für w L , χ L ( w ) = 0 für w L.χLLχL(w)=1wLχL(w)=0wL

Eine Sprache wird als "universeller (geschlossener) Prädiktor" bezeichnet, wennU

LPn>>0:s(L)n=χU(s(L)<n)

Es ist leicht, wenn man L = U c betrachtet . Allerdings U kann rekursiv sein. Betrachten Sie als Beispiel die Sprache, die vom folgenden Algorithmus A festgelegt wurde . Bei gegebener Eingabe w führt A alle möglichen Programme in kurzer Reihenfolge aus, so dass jedes für die Zeit t ( | w | ) ausgeführt werden kann, wobei t eine Funktion des Superpolynomwachstums ist. Sobald es ein Programm R erreicht , das w plus ein oder mehrere Bits ausgibt und nicht anhält, gibt A das erste Bit R ausUPL=UcUAwAt(|w|)tRwARausgegeben nach . Es ist leicht , einfach zu sehen , dass (unter milden Bedingungen auf t ) A immer stoppt und die Sprache , es entscheidet ein universeller Prädiktor ist. A ' s Zeitkomplexität beträgt ca. 2 n t ( n )wtAAs2nt(n)

Wenn , definieren Sie s ( L , a ) durcha{0,1}ωs(L,a)

s ( L , a ) 2 n + 1 = a n

s(L,a)2n=χL(s(L,a)<2n)
s(L,a)2n+1=an

Eine Sprache wird als "universeller offener Prädiktor" bezeichnet, wennV

  1. ist geradewV:|w|
  2. LP,a{0,1}ωn>>0:s(L,a)2n=χV(s(L,a)<2n)

|s<2n|=2n

VPVE

VPV=NPV

Ich bin besonders daran interessiert, entweder ein spezifisches Beispiel für ein solches oder einen Beweis dafür, dass ein solches V unter vernünftigen Annahmen wie PN P nicht existiertVVPNP

LaVuuV

Vanessa
quelle
In Bezug auf die Relativierung funktioniert V = PSPACE.
Tayfun Pay

Antworten:

5

Ich bin mit dem Begriff des universellen Prädiktors nicht vertraut, und ich habe nicht alles befolgt, was Sie geschrieben haben. Insbesondere bin ich Ihrer Skizze des Existenznachweises eines universellen Prädiktors in E nicht gefolgt. Unter der Annahme, dass es einen universellen offenen Prädiktor gibt, der zu E gehört, ist die Antwort auf Ihre Frage positiv. Und ich befürchte, dass Sie vom Grund wahrscheinlich enttäuscht sein werden.

Bearbeiten in Revision 2: Ich habe die Konstruktion als Reaktion auf die zusätzliche Einschränkung in Revision 2 der Frage geändert, aber die allgemeine Idee ist dieselbe: Mischen Sie eine harte Sprache in einen universellen offenen Prädiktor, so dass die Definition des universellen offenen Prädiktors bemerkt den Unterschied nicht.

Sei T = {0 | x | 11 x : x ∈ {0,1} * }. Beachten Sie, dass jedes Wort in T eine gerade Länge hat. Eine wichtige Eigenschaft von T ist, dass kein Wort in T ein richtiges Präfix eines anderen Wortes in T ist . Dies impliziert, dass, wenn die symmetrische Differenz zwischen zwei Sprachen V und W in T enthalten ist , für jede unendliche Folge s ∈ {0,1} ω höchstens ein n vorhanden ist, so dass χ V ( s <2 n ) ≠ ≠W ( s <2 n ) und insbesondere V ist genau dannein universeller offener Prädiktor,wenn W ein universeller offener Prädiktor ist.

Es ist leicht zu erkennen, dass es eine EXPSPACE-vollständige Sprache gibt, die eine Teilmenge von T ist . Sei L eine solche Sprache. Sei V ein universeller offener Prädiktor, der zu E und damit auch zu EXPSPACE gehört. Definieren Sie eine Sprache W = L ∪ ( VT ). Da V ein universeller offener Prädiktor ist und die symmetrische Differenz zwischen V und W in T enthalten ist , ist W auch ein universeller offener Prädiktor. Es ist leicht zu erkennen, dass W EXPSPACE-vollständig ist und daher P W = NP W.= EXPSPACE. Dies schließt daraus, dass W die gewünschte Eigenschaft erfüllt.

Tsuyoshi Ito
quelle
1
Ha! Guter Punkt, aber Sie haben mich aus technischen Gründen erwischt. Ich habe die Definition korrigiert, um festzustellen, dass ein universeller offener Prädiktor nur Wörter mit gerader Länge enthält. "Universal Predictor" ist meine eigene Terminologie. Das Konzept ist von arxiv.org/abs/cs/0606070 inspiriert, aber Legg vermeidet Überlegungen zur Zeitkomplexität
Vanessa
1
@Squark: Hmm, ich denke, dass die Idee, in einer harten Sprache zu mischen, auch mit der überarbeiteten Definition funktioniert und daher denke ich, dass dies nicht nur eine technische Angelegenheit ist, sondern ich muss mehr darüber nachdenken.
Tsuyoshi Ito
3
@ Quark: Ich dachte mehr. :)
Tsuyoshi Ito
OK, das ist keine technische Angelegenheit. Danke!
Vanessa