Pada

Kita tahu bahwa . Dari Teorema Savitch, , dan, dari Space Hierarchy Teorem, . Jadi, karena kita tidak tahu apakah , kita tidak tahu apakah , atau kita tahu itu ? Adakah yang mencoba membuktikan bahwa \ mathcal L ^ 2 \ subseteq \ mathcal P ? Apa hasil terbaru, atau upaya, dengan cara ini? Saya sudah mencoba menulis survei tentang topik ini, tetapi belum menemukan yang relevan.$\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$L ≠ L 2 L ≠ P L 2 ⊆ P L 2 ⊈ P L 2 ⊆ $\mathcal{N\!L}\subseteq\mathcal{L}^2$$\mathcal{L}\neq\mathcal{L}^2$$\mathcal L\neq\mathcal P$$\mathcal L^2\subseteq\mathcal P$$\mathcal L^2\not\subseteq\mathcal P$$\mathcal L^2\subseteq\mathcal P$

Lebih lanjut, apakah ada masalah $\mathcal{N\!P}$ atau bukan $\mathcal{N\!P}$ -lengkapi adalah pertanyaan terbuka, dan keberadaan seperti itu akan menyiratkan $\mathcal L\neq\mathcal{N\!P}$ , karena setiap $\mathcal L$ masalah adalah lengkap untuk $\mathcal L$ . Tapi apakah kita benar-benar tidak tahu itu $\mathcal L\neq\mathcal{N\!P}$ ? Adakah yang mencoba membuktikan ini? Sekali lagi, apa hasil terbaru, atau upaya, dengan cara ini?

Mungkin saya kehilangan sesuatu, atau mencari secara salah, tetapi saya tidak dapat menemukan orang yang mengerjakan pertanyaan $\mathcal L^2\subseteq \mathcal P$ dan $\mathcal L\neq\mathcal{N\!P}$ .

Anda dapat memeriksa makalah berikut:

Lemma terjemahan, waktu polinomial, dan -space$(\log n)^j$ oleh Ronald V. Book (1976).

Gambar 1 dan 2 dalam makalah ini memberikan ringkasan tentang apa yang diketahui dan apa yang tidak diketahui.

Saya memasukkan Teorema 3.10 di koran di sini:

• $DTIME(poly(n)) \neq DSPACE(poly(\log n))$ ;
• untuk setiap , ;D T I M E ( n $j \geq 1$$DTIME(n^j) \neq DSPACE(poly(\log n))$
• untuk setiap , .D T I M E ( n j ) ≠ D S P A C E ( ( log n ) k$j,k \geq 1$$DTIME(n^j) \neq DSPACE( (\log n)^k )$