Apa konsekuensi dari

Kita tahu bahwa $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ dan $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq$ $\mathsf{polyL}$ , di mana $\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n)$ . Kita juga tahu bahwa $\mathsf{polyL} \neq \mathsf{P}$karena yang terakhir memiliki masalah lengkap di bawah ruang reduksi banyak-satu sementara logaritmik tidak (karena teorema hierarki ruang). Dalam rangka untuk memahami hubungan antara $\mathsf{polyL}$ dan $\mathsf{P}$ , mungkin membantu untuk pertama memahami hubungan antara $\mathsf{L}^2$ dan $\mathsf{P}$ .

Apa konsekuensi dari $\mathsf{L}^2 \subseteq \mathsf{P}$ ?

Bagaimana dengan kuat $\mathsf{L}^{k} \subseteq \mathsf{P}$ untuk $k>2$ , atau lemah $\mathsf{L}^{1 + \epsilon} \subseteq \mathsf{P}$ untuk $\epsilon > 0$ ?

Berikut ini adalah konsekuensi yang jelas: akan berarti L ⊊ P dan karena itu L ≠ P .$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$$\mathsf{L} \subsetneq \mathsf{P}$$\mathsf{L} \neq \mathsf{P}$

Dengan teorema hierarki ruang, . Jika L 1 + ε ⊆ P kemudian 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}}$

akan menyangkalHipotesis Waktu Eksponensial.$\L^2 \subseteq \P$

Jika maka dengan argumen padding D S P A C E ( n ) ⊆ D T I M E ( 2 O ( $\L^2 \subseteq \P$ . Ini berarti bahwa masalah kepuasanSAT∈DSPACE(n) dapat diputuskan dalam2o(n)langkah, menyangkal Hipotesis Waktu Eksponensial.$\DSPACE(n) \subseteq \DTIME(2^{O(\sqrt n)})$$\mathsf{SAT} \in \DSPACE(n)$$2^{o(n)}$

Secara umum, untuk k ≥ 1 menyiratkan S A T ∈ D S P A 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}})})$

(Jawaban ini diperluas dari komentar oleh @MichaelWehar.)

Kelompok isomorfisma (dengan kelompok yang diberikan sebagai tabel perkalian) akan berada di P. Lipton, Snyder, dan Zalcstein menunjukkan masalah ini adalah dalam , tetapi masih terbuka apakah itu dalam P. Batas atas saat ini terbaik adalah n O ( log n ) -waktu, dan karena mengurangi ke grafik isomorfisme, berdiri sebagai hambatan yang signifikan untuk menempatkan iso grafik ke dalam P.$\mathsf{L}^2$$n^{O(\log n)}$

Membuat saya bertanya-tanya apa masalah alami dan penting lainnya yang akan terjadi pada: yaitu di tetapi dengan waktu yang paling dikenal sebagai kuasi polinomial batas atas.$\mathsf{L}^2$

Klaim: Jika untuk beberapa k > 2 , maka P ≠ log ( C F L ) dan P ≠ N L .$L^k \subseteq P$$k > 2$$P \neq \log(CFL)$$P \neq NL$

Misalkan untuk beberapa k > 2 .$L^k \subseteq P$$k > 2$

Dari " Batas memori untuk pengenalan bahasa yang bebas konteks dan peka konteks ", kita tahu bahwa . Dengan teorema hierarki ruang, kita tahu bahwa 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))$

Karena itu, kita dapatkan .$\log(CFL) \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$

Juga, oleh Teorema Savitch, kita tahu bahwa . Karena itu, kita dapatkan$NL \subseteq L^2$ .$NL \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$