Ich frage mich, ob es eine Rechtfertigung dafür gibt, zu glauben, dass oder dass N L ≠ L ist .
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 ?
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:
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".. 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.
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 .