Jakie są konsekwencje

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

Oczywistą konsekwencją jest: implikuje L ⊊ P, a zatem L ≠ $\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 L 1 + ε ⊆ P następnie L ⊊ L 1 + ε ⊆ P .$\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}$

$\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 D S P A C E ( n ) ⊆ D T I M E ( 2 O ( $\L^2 \subseteq \P$ . Oznacza to, że problem zadowalalnościSAT∈DSPACE(n) można rozwiązać w2o(n$\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 k ≥ 1 oznacza S T ∈ D S P C e ( n ) ⊆ D T I M E ( 2 O ( N $\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.)

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 n O ( log n ) -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$

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

Załóżmy, że dla niektórych k > $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 D S P A C E ( log 2 ( n ) ) ⊊ D S P A C E ( log k ( n ) ) .$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ę N L ⊆ D S P A C E ( log 2 ( n ) ) ⊊ D S P C E ( log k ( n ) ) ⊆ P .$NL \subseteq L^2$$NL \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$