Warum betrachten wir den Log-Raum als Modell für eine effiziente Berechnung (anstelle des Polylog-Raums)?

49

Dies könnte eher eine subjektive Frage als eine konkrete Antwort sein, aber trotzdem.

In der Komplexitätstheorie untersuchen wir den Begriff effizienter Berechnungen. Es gibt Klassen wie für Polynomial Time und für Log Space . Beide werden als eine Art "Effizienz" angesehen und erfassen die Schwierigkeiten einiger Probleme ziemlich gut.LPL

Es gibt jedoch einen Unterschied zwischen und : Während die Polynomzeit als die Vereinigung von Problemen definiert ist, die in der für jede Konstante läuft , das ist,L P O ( n k ) kPLPO(nk)k

P=k0TIME[nk] ,

Der Protokollbereich ist definiert als . Wenn wir die Definition von , wird esS P A C E [ log n ] PLSPACE[logn]P

PolyL=k0SPACE[logkn] ,

Dabei wird als Klasse des Polylog-Space bezeichnet . Meine Frage ist:PolyL

Warum verwenden wir den Protokollbereich als Begriff für eine effiziente Berechnung anstelle des Polylog-Bereichs?

Ein Hauptproblem kann die Gesamtheit der Problemstellungen sein. Unter logspace many-one reductions haben sowohl als auch vollständige Probleme. Wenn dagegen unter solchen Reduktionen vollständige Probleme hat, dann hätten wir dem widersprochen. Aber was ist, wenn wir zu den Polylog-Reduzierungen wechseln? Können wir solche Probleme vermeiden? Wenn wir im Allgemeinen versuchen, in den Begriff der Effizienz , und (falls erforderlich) einige der Definitionen ändern, um alle guten Eigenschaften zu erhalten, die eine "nette" Klasse haben sollte, wie weit können wir gehen?L P o l y L P o l y LPLPolyLPolyL

Gibt es theoretische und / oder praktische Gründe für die Verwendung von Protokollspeicher anstelle von Protokollspeicher?

Hsien-Chih Chang 張顯 張顯
quelle
Hsien-Chih, nette Frage.
Mohammad Al-Turkistany
9
Es ist die bekannte . Soweit mir persönlich bekannt ist, ist die genaue Beziehung zwischen und unklar. Wie in ist es möglich, dass einige Probleme in lösbar sind, die in und umgekehrt nicht lösbar sind . (Dies spricht zum Teil für Ihre Frage, warum ein ungerader Kandidat für eine effiziente Berechnung ist.) Weitere zu finden Sie in Papadimitrious Komplexitätslehrbuch , insbesondere in den Übungen und der Diskussion am Ende von Kapitel 16.P P o l y L p o l y L P p o l y LpolyLPPpolyLpolyLP polyLpolyL
Daniel Apon
Noch ein kurzer Kommentar zu einem kleinen Teil Ihrer allgemeinen Frage: Polylog- sagen nicht viel über , aus den gleichen Gründen sagen polynomiale nicht viel über . polyLP
Daniel Apon
@ Daniel Apon: Vielen Dank, dass Sie das Buch erwähnt haben, und es ist schön :) Für den zweiten Kommentar können wir nach demselben Argument lineare Verkleinerungen anstelle von polynomiellen verwenden, um mehr Informationen über , oder? P
Hsien-Chih Chang 張顯 張顯
Chih Chang: Nun, ich kenne keine linearen Zeitreduktionen, aber es gibt andere interessante Begriffe von Reduktionen , die Auskunft über die Komplexität in . P
Daniel Apon

Antworten:

51

Die kleinste Klasse, die lineare Zeit enthält und unter Subroutinen geschlossen ist, ist P. Die kleinste Klasse, die Protokollspeicher enthält und unter Subroutinen geschlossen ist, ist noch Protokollspeicher. Daher sind P und L die kleinsten robusten Klassen für Zeit und Raum, weshalb sie sich für die Modellierung effizienter Berechnungen als richtig erweisen.

Lance Fortnow
quelle
4
Dies scheint die beste Antwort auf die tatsächlich gestellte Frage zu sein.
Derrick Stolee
1
Unter all diesen guten Antworten denke ich, dass die Antwort von Lance die genaueste ist, und ich werde sie akzeptieren. Trotzdem vielen Dank für jede nachdenkliche Antwort!
Hsien-Chih Chang 張顯 張顯
1
Auch ist es ein offenes Problem, ob P = L ist.
Diego de Estrada
25

Ein Problem ist, dass nicht bekannt ist, ob . Damit wird der Begriff der Effizienz ziemlich zunichte gemacht. In einer anderen Anmerkung: Bestimmen, ob der Schnittpunkt der Sprachen von erkannt wirdSPACE[log2n]Pist NSPACE [ log k n ] -vollständig unter logspace Reductions[Lange-Rossmanith] log k - 1 ( n ) -Automatennicht leer ist. Vielleicht gibt es einige ähnliche Probleme für den deterministischen Polylograum.logk1(n)NSPACE[logkn]-complete

Die Klasse wurde in der Vergangenheit untersucht. [Cook] hatbewiesen, dass DCFL PLOSS ist . Wie von Derrick Stolee bemerkt, ist diese Klasse jetzt als SC 2 bekannt und wurde auf SC k verallgemeinert. Weitere Informationenhier.PLOSS=kTISP[nk,klog2n]DCFLPLOSSSC2SCk

Michael Blondin
quelle
2
Können wir anstelle von P verwenden ? QuasiP=k0TIME[2logkn]P
Hsien-Chih Chang 張顯 張顯
Ist dies ein bekanntes offenes Problem? Könnten Sie eine Referenz angeben?
Mohammad Al-Turkistany
Ihre PLOSS-Klasse entspricht in modernen Begriffen der . SC steht für "Steve's Class", wahrscheinlich für das Ergebnis von Cook's, das Sie zitieren. SC2
Derrick Stolee
5
Beachten Sie, dass SC von Nick Pippenger in einer angeblich gegenseitigen Vereinbarung mit Steve Cook benannt wurde, um NC nach ihm zu benennen :)
Suresh Venkat
so ist das richtig: da eine viel wichtige Klasse darstellt Effizienz ist, so dass anstelle von der Änderung P zu Q u a s i P , um fit p o l y L , verwenden wir L , um fit zu P ? Wenn dann zu einem bestimmten Zeitpunkt die Beziehung S P A C E [ log k n ] P für einige k bewiesen wird, wird die Klasse L k wichtiger? PPQuasiPpolyLLPSPACE[logkn]PkLk
Hsien-Chih Chang 張顯 張顯
20

Der Protokollraum garantiert die Polynomzeit, da es höchstens Konfigurationen für eine gegebene Protokollraum-Turing-Maschine gibt. Die vollständigen Probleme von Undirected Reach und Directed Reach (für L bzw. NL) sind sehr "nett" zu bedenken.2O(logn)=poly(n)

Beachten Sie, dass Ihre Definition von PolyL nach dem Satz von Savitch auch PolyL = NPolyL ergibt, da .NSPACE[logkn]SPACE[log2kn]

SCk=TISP[poly(n),logkn]

Derrick Stolee
quelle
polyLNLpolyL
{1}
Sie haben Recht, entschuldigen Sie die dumme Frage :(
Hsien-Chih Chang 張顯 張顯
13

Ich finde alle anderen Antworten sehr gut; Ich werde versuchen, eine andere Perspektive auf das Problem zu geben.

Ich weiß nicht, wie gut P-Modelle in der realen Welt "effizient" rechnen, aber wir mögen die Klasse wegen ihrer guten Schlusseigenschaften und anderer mathematischer Gründe. In ähnlicher Weise ist L auch aus den oben genannten Gründen eine nette Klasse.

Wie Sie jedoch bemerkt haben, ist PolyL auch effizient, wenn wir unsere Definition von "effizient" zu quasi-polynomieller Zeit lockern. Wir könnten die Komplexitätstheorie diskutieren, bei der Klassen, die mit einem logarithmischen Wert für eine Ressource definiert wurden, stattdessen Polylog-Ressourcen verwenden können. Dementsprechend würden wir auch unsere Definitionen von NC, NL usw. lockern, um stattdessen quasi-polynomiale Schaltkreise zuzulassen. Wenn wir dies tun, stimmen NC 1 , L, NL und NC alle mit der Klasse PolyL überein. In diesem Sinne ist PolyL eine robuste Klasse, da viele natürliche Klassen damit übereinstimmen. Weitere Informationen zur Komplexitätstheorie mit log -> Polylog und Polynom -> Quasi-Polynom finden Sie unter Quasipolynomial size circuit classes von Barrington.

Ein weiterer Grund, polyL oder ähnliche Klassen wie quasi-AC 0 zu studieren, ist, dass, während eine Orakeltrennung zwischen (sagen wir) ParityP und PH impliziert, dass PARITY nicht in AC 0 enthalten ist , die umgekehrte Implikation nicht als wahr bekannt ist. Andererseits ist PARITY in quasi-AC 0 nur dann nicht enthalten, wenn zwischen ParityP und PH eine Orakeltrennung besteht. Ebenso unterscheiden sich die Klassen Quasi-TC 0 und Quasi-AC 0 nur dann, wenn zwischen CH und PH eine Orakeltrennung besteht. So werden die üblichen Komplexitätsklassen wie PH, ModPH, CH usw., wenn sie durch ein Exponential verkleinert werden, um Orakelergebnisse zu beweisen, zu quasi-polynomiellen Versionen der üblichen Klassen AC 0 , ACC 0 und TCJeweils 0 . In ähnlicher Weise kann das in Todas Theorem verwendete Argument (PH ist in PP enthalten ) verwendet werden, um zu zeigen, dass Quasi-AC 0 in Tiefe-3-Quasi-TC 0 enthalten ist . (Ich weiß nicht, ob für die üblichen Versionen dieser Klassen dieselbe Schlussfolgerung bekannt ist. Ich habe gesehen, dass dies in einigen Artikeln als offenes Problem aufgeführt ist.)

Robin Kothari
quelle
1
Ihre Antwort hilft wirklich, danke, dass Sie uns Ihre Meinung mitteilen. Ich bin erstaunt, dass Quasi-etwas VIEL studiert worden ist !!
Hsien-Chih Chang 張顯 張顯