Jakie są konsekwencje

46

Wiemy, że $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ i że $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq$ $\mathsf{polyL}$ , gdzie $\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n)$ . Wiadomo również, że $\mathsf{polyL} \neq \mathsf{P}$ ponieważ ten drugi ma całkowite problemy w przestrzeni logarytmicznej, wielokrotne redukcje jeden-jedynki, podczas gdy ten drugi nie (ze względu na twierdzenie o hierarchii przestrzeni). W celu zrozumienia zależności między $\mathsf{polyL}$ i $\mathsf{P}$ , może pomóc zrozumieć najpierw związek pomiędzy $\mathsf{L}^2$ i $\mathsf{P}$ .

Jakie są konsekwencje $\mathsf{L}^2 \subseteq \mathsf{P}$ ?

Co z silniejszym $\mathsf{L}^{k} \subseteq \mathsf{P}$ dla $k>2$ lub słabszym $\mathsf{L}^{1 + \epsilon} \subseteq \mathsf{P}$ dla $\epsilon > 0$ ?

— argentpepper
źródło

4

@OrMeir Niedawno dodałem wyjaśnienie tego faktu do artykułu Wikipedii dotyczącego poliL .

— argentpepper

13

Myślę, że następujące konsekwencje są oczywiste, a zwłaszcza nie zaskakujące:

L^{2} \subseteq P

$L^2 \subseteq P$ implikuje, że

L \neq P

$L \neq P$ , ponieważ w przeciwnym razie byłoby to sprzeczne z hierarchią przestrzeni

L ⊊ L^{2}

$L \subsetneq L^2$ .

— Sajin Koroth,

12

Dobre pytanie! Myślę, że to zdecydowanie warte nagrody. Przy okazji, tutaj jest prosta obserwacja, jeśli

L^{2} \subseteq P

$L^2 \subseteq P$ , to

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})})$ . Dlatego mamy bardziej wydajny algorytm dla CNF-SAT i odrzucamy ETH (hipoteza wykładnicza czasu).

— Michael Wehar

3

Po komentarzu @ MichaelWehar, implikacja wynika ze standardowego argumentu wypełniającego, który rozciąga się na słabsze hipotezy: jeśli

jest w

, to każdy problem, który można rozwiązać w przestrzeni liniowej (w tym problem satysfakcji), można rozwiązać w czasie

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: Myślę, że twój komentarz, a także kontynuacja Michaela Wehara (i argentpeppera) powinny być odpowiedziami ...

— Joshua Grochow

26

Oczywistą konsekwencją jest: implikuje a zatem $\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ $\mathsf{L} \subsetneq \mathsf{P}$ $\mathsf{L} \neq \mathsf{P}$ .

Według twierdzenia o hierarchii przestrzeni . Jeśli następnie . $\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
źródło

Mały przypis: Jeżeli

, to mamy

lub

.

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}}$

obali hipotezęowykładniczym czasie $\L^2 \subseteq \P$ .

Jeżeli to za pomocą argumentu wypełniającego $\L^2 \subseteq \P$ . Oznacza to, że problem zadowalalności można rozwiązać w $\DSPACE(n) \subseteq \DTIME(2^{O(\sqrt n)})$ $\mathsf{SAT} \in \DSPACE(n)$ $2^{o(n)}$ krokach, obalając hipotezę o wykładniczym czasie.

Bardziej ogólnie, dla oznacza $\DSPACE(\log^{k} n) \subseteq \P$ $k\geq1$ . $\mathsf{SAT} \in \DSPACE(n) \subseteq \DTIME(2^{O(n^{\frac{1}{k}})})$

(Ta odpowiedź została rozwinięta z komentarza @MichaelWehar.)

— argentpepper
źródło

Dziękujemy za rozwinięcie komentarza! Doceniam to. :)

— Michael Wehar,

1

Ponadto ostatnia hipoteza sugeruje również, że

jest w 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

Grupowy izomorfizm (z grupami podanymi jako tabliczki mnożenia) występowałby u P. Liptona, Snydera, a Zalcstein pokazał, że ten problem występuje w , ale nadal jest otwarte, czy występuje w P. Najlepszy obecnie górny limit to -czas, a ponieważ sprowadza się do izomorfizmu grafów, stanowi znaczącą przeszkodę dla umieszczenia wykresu iso w P. $\mathsf{L}^2$ $n^{O(\log n)}$

Zastanawiam się, do jakich innych naturalnych i ważnych problemów miałoby to zastosowanie: to znaczy w ale z ich najlepiej znanym czasem quasi-wielomianem. $\mathsf{L}^2$

— Joshua Grochow
źródło

1

Mówiąc dokładniej, bardziej ogólnym problemem quasi-grupowego izomorfizmu jest

, który jest podklasą

.

β_{2} F O L L

$\beta_2 \mathsf{FOLL}$

L^{2}

$\mathsf{L}^2$

— argentpepper

1

Również problem rang grupy (biorąc pod uwagę skończoną grupę G jako tabliczkę mnożenia i liczbę całkowitą k , czy G ma zbiór generowania liczności k ?) Również ma tę właściwość. Algorytm jest tylko ponad podzbiorów G o liczności k ale używa dwóch istotnych faktów: (1) każda grupa skończonego ma prądotwórczego wielkości logarytmicznej oraz (2) członków podgrupy jest

, która jest równa

.

S L

$\mathsf{SL}$

L

$\mathsf{L}$

— argentpepper

1

Twierdzenie: Jeśli jakiegoś , a i . $L^k \subseteq P$ $k > 2$ $P \neq \log(CFL)$ $P \neq NL$

Załóżmy, że dla niektórych $L^k \subseteq P$ $k > 2$ .

Z „ Granic pamięci dla rozpoznawania języków bezkontekstowych i kontekstowych ” wiemy, że . Z twierdzenia o hierarchii przestrzeni wiemy, że . $CFL \subseteq DSPACE(\log^2(n))$ $DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n))$

Dlatego otrzymujemy $\log(CFL) \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$ .

Również z twierdzenia Savitcha wiemy, że . Dlatego się . $NL \subseteq L^2$ $NL \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$

— Michael Wehar
źródło