Quais são as consequências de

Sabemos que $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ e que $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq$ $\mathsf{polyL}$ , em que $\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n)$ . Nós também sabe que $\mathsf{polyL} \neq \mathsf{P}$porque o último tem problemas completos no espaço logarítmico, muitas reduções, enquanto o primeiro não (devido ao teorema da hierarquia espacial). A fim de entender a relação entre a $\mathsf{polyL}$ e $\mathsf{P}$ , que pode ajudar a primeira compreender a relação entre $\mathsf{L}^2$ e $\mathsf{P}$ .

Quais são as consequências de $\mathsf{L}^2 \subseteq \mathsf{P}$ ?

E quanto mais forte $\mathsf{L}^{k} \subseteq \mathsf{P}$ para $k>2$ , ou o mais fraco $\mathsf{L}^{1 + \epsilon} \subseteq \mathsf{P}$ para $\epsilon > 0$ ?

A consequência a seguir é óbvia: implicaria e, portanto, .$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$$\mathsf{L} \subsetneq \mathsf{P}$$\mathsf{L} \neq \mathsf{P}$

Pelo teorema da hierarquia espacial, . Se então .$\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}}$

$\L^2 \subseteq \P$ refutaria a hipótese do tempo exponencial .

Se seguida, por um argumento de preenchimento . Isso significa que o problema de satisfação pode ser decidido em etapas, refutando a hipótese do tempo exponencial.$\L^2 \subseteq \P$ $\DSPACE(n) \subseteq \DTIME(2^{O(\sqrt n)})$$\mathsf{SAT} \in \DSPACE(n)$$2^{o(n)}$

De maneira mais geral, para implica .$\DSPACE(\log^{k} n) \subseteq \P$$k\geq1$$\mathsf{SAT} \in \DSPACE(n) \subseteq \DTIME(2^{O(n^{\frac{1}{k}})})$

(Esta resposta foi expandida a partir de um comentário de @MichaelWehar.)

O isomorfismo de grupo (com grupos dados como tabelas de multiplicação) estaria em P. Lipton, Snyder e Zalcstein mostrou que esse problema está em , mas ainda está aberto se está em P. O melhor limite superior atual O tempo é e, como se reduz ao isomorfismo do gráfico, representa um obstáculo significativo para colocar o iso do gráfico em P.$\mathsf{L}^2$$n^{O(\log n)}$

Me faz pensar em que outros problemas naturais e importantes isso se aplicaria: isto é, em mas com seu tempo mais conhecido quase polinomial no limite superior.$\mathsf{L}^2$

Reivindicação: Se para alguns , e .$L^k \subseteq P$$k > 2$$P \neq \log(CFL)$$P \neq NL$

Suponha que para alguns .$L^k \subseteq P$$k > 2$

Em " Limites de memória para reconhecimento de linguagens livres de contexto e sensíveis ao contexto ", sabemos que . Pelo teorema da hierarquia espacial, sabemos que .$CFL \subseteq DSPACE(\log^2(n))$$DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n))$

Por conseguinte, temos .$\log(CFL) \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$

Além disso, pelo Teorema de Savitch, sabemos que . Portanto, temos .$NL \subseteq L^2$$NL \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$