Was sind die Folgen von

46

Wir wissen , dass $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ und dass $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq$ $\mathsf{polyL}$ , wobei $\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n)$ . Wir wissen auch , dass $\mathsf{polyL} \neq \mathsf{P}$ weil letztere unter logarithmischen Raum-Viel-Eins-Reduzierungen vollständige Probleme haben, während erstere dies nicht tut (aufgrund des Raumhierarchiesatzes). Um die Beziehung zwischen dem zu verstehen , $\mathsf{polyL}$ und $\mathsf{P}$ , kann es helfen , die Beziehung zwischen dem ersten zu verstehen $\mathsf{L}^2$ und $\mathsf{P}$ .

Was sind die Folgen von $\mathsf{L}^2 \subseteq \mathsf{P}$ ?

Was ist mit dem stärkeren $\mathsf{L}^{k} \subseteq \mathsf{P}$ für $k>2$ , oder den schwächeren $\mathsf{L}^{1 + \epsilon} \subseteq \mathsf{P}$ für $\epsilon > 0$ ?

cc.complexity-theory complexity-classes conditional-results structural-complexity Argentpepper
quelle

4

@OrMeir Ich habe kürzlich dem Wikipedia-Artikel für polyL eine Erklärung für diesen Umstand hinzugefügt .

Argentpepper

13

L^{2} \subseteq P

$L^2 \subseteq P$

L \neq P

$L \neq P$

L ⊊ L^{2}

$L \subsetneq L^2$

12

Gute Frage! Ich denke, es ist definitiv eine Prämie wert. Übrigens ist hier eine einfache Beobachtung, wenn , dann . Daher haben wir einen effizienteren Algorithmus für CNF-SAT und wir widerlegen ETH (Exponential Time Hypothesis).

L^{2} \subseteq P

$L^2 \subseteq P$

D S P A C E (n) \subseteq D T I M E (2^{O (\sqrt{n})})

$DSPACE(n) \subseteq DTIME(2^{O(\sqrt{n})})$

Michael Wehar

3

Nach @ MichaelWehars Kommentar folgt die Implikation aus einem Standard- Auffüllargument, das sich auf schwächere Hypothesen erstreckt: Wenn in , kann jedes Problem, das im linearen Raum gelöst werden kann (einschließlich des Erfüllbarkeitsproblems), gelöst werden gelöst werden in der Zeit .

L^{1 + ϵ}

$L^{1 + \epsilon}$

P

$P$

2^{O (n^{\frac{1}{1 + ϵ}})}

$2^{O\left(n^{\frac{1}{1 + \epsilon}}\right)}$

Argentpepper

3

@SajinKoroth: Ich denke, Ihr Kommentar sowie Michael Wehars (und Argentpeppers Follow-up) sollten Antworten sein ...

Joshua Grochow

26

Das Folgende ist eine offensichtliche Konsequenz: impliziert und daher . $\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ $\mathsf{L} \subsetneq \mathsf{P}$ $\mathsf{L} \neq \mathsf{P}$

Nach dem ist . Wenn dann . $\forall \epsilon > 0: \mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon}$ $\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ $\mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$

Sajin Koroth
quelle

Kleine Fußnote: Wenn , dann haben wir oder .

P \neq L

$P \neq L$

P \neq N L

$P \neq NL$

N L \neq L

$NL \neq L$

Michael Wehar

27

$\newcommand{\DSPACE}{\mathsf{DSPACE}} \newcommand{\L}{\mathsf{L}} \newcommand{\P}{\mathsf{P}} \newcommand{\DTIME}{\mathsf{DTIME}}$

$\L^2 \subseteq \P$ würde die Exponentialzeithypothese widerlegen .

Wenn dann durch ein Auffüllargument . Dies bedeutet, dass das Erfüllbarkeitsproblem in Schritten entschieden werden kann, wobei die Exponentialzeithypothese widerlegt wird. $\L^2 \subseteq \P$ $\DSPACE(n) \subseteq \DTIME(2^{O(\sqrt n)})$ $\mathsf{SAT} \in \DSPACE(n)$ $2^{o(n)}$

Im Allgemeinen impliziert für . $\DSPACE(\log^{k} n) \subseteq \P$ $k\geq1$ $\mathsf{SAT} \in \DSPACE(n) \subseteq \DTIME(2^{O(n^{\frac{1}{k}})})$

(Diese Antwort wurde aus einem Kommentar von @MichaelWehar erweitert.)

Argentpepper
quelle

Vielen Dank für die Erweiterung des Kommentars! Ich schätze es. :)

Michael Wehar

1

Darüber hinaus impliziert die letzte Hypothese auch, dass sich in DSPACE ( ) DTIME ( .

Q B F

$QBF$

n

$n$

\subseteq

$\subseteq$

2^{O (n^{\frac{1}{k}})}

$2^{O(n^{\frac{1}{k}})}$

Michael Wehar

8

Gruppenisomorphismus (mit Gruppen, die als Multiplikationstabellen angegeben sind) wurde in P. Lipton, Snyder und Zalcstein gezeigt, dass dieses Problem in , aber es ist immer noch offen, ob es sich in P. The best current upper bound befindet ist -Zeit, und da es sich auf Graph-Isomorphismus reduziert, ist es ein bedeutendes Hindernis, Graph-Iso in P zu setzen. $\mathsf{L}^2$ $n^{O(\log n)}$

Ich frage mich, auf welche anderen natürlichen und wichtigen Probleme dies zutreffen würde: nämlich in aber mit ihrem bekanntesten Quasi-Polynom. $\mathsf{L}^2$

Joshua Grochow
quelle

1

Das allgemeinere Problem des Quasigruppen-Isomorphismus liegt in , einer Unterklasse von .

β_{2} F O L L

$\beta_2 \mathsf{FOLL}$

L^{2}

$\mathsf{L}^2$

Argentpepper

1

Auch das Gruppenrangproblem (wenn eine endliche Gruppe G als Multiplikationstabelle und eine ganze Zahl k gegeben sind , hat G eine generierende Menge von Kardinalitäten k ?) Hat diese Eigenschaft. Der Algorithmus ist nur eine Suche über die Untergruppen von G der Kardinalität k , verwendet jedoch zwei wichtige Fakten: (1) Jede endliche Gruppe hat einen Satz logarithmischer Größe und (2) die Untergruppenzugehörigkeit ist in , was gleich .

S L

$\mathsf{SL}$

L

$\mathsf{L}$

Argentpepper

1

Behauptung: Wenn für etwas , dann und . $L^k \subseteq P$ $k > 2$ $P \neq \log(CFL)$ $P \neq NL$

Angenommen, für ein . $L^k \subseteq P$ $k > 2$

Aus " Speichergrenzen für die Erkennung kontextfreier und kontextsensitiver Sprachen " wissen wir, dass . Durch den Satz der Raumhierarchie wissen wir, dass . $CFL \subseteq DSPACE(\log^2(n))$ $DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n))$

Daher erhalten wir . $\log(CFL) \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$

Nach dem Satz von Savitch wissen wir auch, dass . Daher erhalten wir . $NL \subseteq L^2$ $NL \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$

Michael Wehar
quelle

Was sind die Folgen von

Antworten: