L / P / PSpace vs P / NP

1979 schrieben Hopcroft / Ullman , dass L ⊆ P ⊆ NP ⊆ PSpace bekannt ist, aber L ⊊ PSpace die einzig richtige (& triviale) bekannte Einschließung ist, obwohl alle als richtige Einschließungen vermutet werden und "wo die Dinge noch stehen" ~ 4 Jahrzehnte später .

seitdem gibt es bekannte Verbindungen zwischen L L P, P ⊊ PSpace und P ⊊ NP? Wird angenommen, dass sie alle noch unabhängig sind, oder gibt es Anzeichen für eine Interdependenz?

Motivation: diese Frage teilweise durch die jüngsten inspiriert Backurs-Indyk Ergebnisse binden SETH bis O (n ² ) Editierdistanz. SETH ist die Exponentialzeit und die Bearbeitungsentfernung ist PTime. (& auch etwas die Frage, ob man untere Schranken beweist, indem man obere Schranken beweist )

$L \subsetneq PSPACE$

Die jüngste Arbeit zu `` Fine-Grained Complexity ", wie das Edit Distance-Ergebnis von Backurs und Indyk, zeigt, dass wir keine korrekten Containments wie . Insbesondere ist SETH ein viel stärkeres Vermutung als , mehr oder weniger die besagt , dass CNF-SAT erfordert Zeit (nicht nur super-Polynom - Zeit). Im Rahmen dieser stärkeren Vermutung, wenn Sie einen zeigen Reduktion von CNF SAT zu Problemen in (wie Edit Distance), dann erhalten Sie eine bedingte Untergrenze basierend auf SETH. Also, die Unterscheidungen, mit denen sich diese Arbeiten beschäftigen (dh vs.$P\neq NP$$P \neq NP$$2^n$$2^{n/k}$$P$$\Omega(n^k)$$2^{n}$$2^{(1-\delta)n}$) sind viel strenger als die in der Post erwähnten Unterschiede zwischen den traditionellen Komplexitätsklassen.

In ähnlicher Weise benötigen wir zum Beweisen von Schaltungsuntergrenzen durch Ergeben schnellerer Erfüllbarkeitsalgorithmen im Allgemeinen nur fein abgestimmte Verbesserungen gegenüber den trivialen -Algorithmen, um Untergrenzen zu ergeben. Zum Beispiel würde ein Algorithmus für CircuitSAT auf Schaltungen mit Gattern beweisen .$O^\star(2^n)$$2^{n}poly(n^k)/n^{\omega(1)}$$n^k$$NEXP \not \subseteq P/poly$