Gibt es einen Grund zu der Annahme, dass

22

Ich frage mich, ob es eine Rechtfertigung dafür gibt, zu glauben, dass oder dass N L L ist .NL=LNLL

Es ist bekannt, dass . Die Literatur zur Derandomisierung von R L ist ziemlich überzeugend, dass R L = L ist . Kennt jemand einige Artikel oder Ideen, die davon überzeugen, dass N L L ?NLL2RLRL=LNLL

Klim
quelle

Antworten:

30

Zuerst lassen Sie mich zitieren Skepsis , dass . Da gezeigt wurde, dass die Konnektivität ungerichteter Graphen in L (Reingold) und N L = c o N L (Immerman-Szelepcsényi) ist, glaube ich, dass das Vertrauen in L N L nur abgenommen hat. Einige prominente Forscher hatten noch nie einen starken Glauben. Zum Beispiel hat Juris Hartmanis (Gründer der CS-Abteilung bei Cornell and Turing Award Gewinner) gesagt:LNLLNL=coNLLNL

Wir glauben, dass NLOGSPACE sich von LOGSPACE unterscheidet, jedoch nicht mit der gleichen Überzeugung wie für die anderen Komplexitätsklassen. (Quelle)

Ich weiß, dass er in der Literatur bereits in den siebziger Jahren ähnliche Dinge gesagt hat.

Es gibt einige Beweise für , obwohl es sich um Indizien handelt. Es gab Arbeit zu beweisen Raumgrenzen für senken s - t - Konnektivität (das kanonische N L -komplette Problem) in eingeschränkten Rechenmodellen. Diese Modelle sind stark genug, um den Algorithmus des Savitch-Theorems (der einen O ( log 2 n ) -Raumalgorithmus ergibt) auszuführen, aber nachweislich nicht stark genug, um asymptotisch besser zu sein. Weitere Informationen finden Sie im Artikel "Enge untere Schranken für st-Konnektivität beim NNJAG-Modell".L=NLstNLO(log2n). Diese NNJAG unteren Grenzen zeigen , dass, wenn es möglich ist Savitch Theorem zu schlagen und sogar bekommen , wird man sicherlich mit einem Algorithmus zu kommen, die von Savitch sehr unterschiedlich ist.NLSPACE[o(log2n)]

Dennoch kenne ich keine unwahrscheinlichen, unerwarteten formalen Konsequenzen, die sich aus (mit Ausnahme der offensichtlichen). Dies liegt wiederum in erster Linie daran, dass wir bereits Dinge wie N L = c o N L kennen .L=NLNL=coNL

Ryan Williams
quelle
3
Ryan, können die Modelle, in denen Sie die untere Grenze von nachweisen können, ungerichtete Konnektivität im O- Raum ( log n ) bieten ? Wenn es sich um uneinheitliche Modelle handelt, sollte es meiner Meinung nach einfach sein, einen Algorithmus zu implementieren, der auf universellen Durchquerungssequenzen basiert, selbst in einem sehr eingeschränkten ModellΩ(log2n)O(logn)
Luca Trevisan,
@Luca, zitiert das Papier Ryan von Edmonds et al. stellt fest, dass ungerichtete Konnektivität im -Raum und in der Polynomzeit durch einen zufälligen Algorithmus unter Verwendung universeller Durchquerungssequenzen gelöst werden kann . Ich vermute, dass es "a la" Reingold während des Aufenthalts im NNJAG-Modell derandomisiert werden kann, aber ich habe nicht überprüft. O(logn)
Arnab
1
Ich denke, das Modell kann ungerichtete Konnektivität auf regulären Graphen im Raum ausführen. Seite 4 gibt eine Beschreibung des Modells. Wir dürfen p Kieselsteine ​​auf den Knoten des Graphen bewegen (für uns sei p = 1 ), q "Zustände" und eine Übergangsfunktion, die einen Zustand und einen Index eines Kieselknotens annimmt und den Index einer Kante ausgibt den Kiesel entlang bewegen. (Die Kanten eines Scheitelpunkts v sind mit 0 , , d indiziert .) Mit q = n O ( 1 )O(logn)pp=1qv0,,dq=nO(1)Zustände, die wir eine universelle Traversal-Sequenz codieren können. Die Speicherplatznutzung eines NNJAG ist definiert als was in diesem Fall O ( log n ) ist . plogn+logqO(logn)
Ryan Williams