Apa hubungan dugaan antara bahasa P (PTime) dan Tipe 1 (peka konteks)?

Tidak diketahui apakah atau P ⊈ C S L , di mana$P\subseteq CSL$$P\not\subseteq CSL$

• adalah himpunan semua bahasa yang dapat ditentukan dalam waktu polinomial pada mesin Turing deterministik, dan$P$
• adalah kelas bahasa konteks-sensitif, yang dikenal setara dengan N S P A C E ( O ( n ) ) , bahasa yang diputuskan oleh automata terikat-linear.$CSL$$NSPACE(O(n))$

Untuk banyak pertanyaan terbuka, ada kecenderungan menuju satu jawaban ( ala "kebanyakan ahli percaya bahwa "). Apakah ada sesuatu seperti ini untuk pertanyaan ini?$P\neq NP$

Secara khusus, akankah salah satu jawaban memiliki konsekuensi yang tidak terduga? Saya hanya bisa melihat konsekuensi yang diharapkan (tetapi tidak terbukti):

• Jika , maka P ⊆ N S P A C E ( O ( n ) ) ⊊ N S P A C E ( O ( n 2 ) ) (teorema hierarki ruang), maka P ⊊ P S p a c e .$P\subseteq CSL$$P\subseteq NSPACE(O(n))\subsetneq NSPACE(O(n^2))$$P\subsetneq PSpace$
• Jika , maka ada bahasa l ∈ P ∖ N S P A C E ( O ( n ) ) dan oleh karena itu l ∈ P ∖ N L , maka N L ⊊ P .$P\not\subseteq CSL$$l\in P\setminus NSPACE(O(n))$$l\in P\setminus NL$$NL\subsetneq P$

(Pengakuan: Konsekuensi kedua dari keduanya ditunjukkan oleh Yuval Filmus di /cs/69614/ )

$\mathrm{P\subseteq CSL}$$\mathrm{P\subseteq DSPACE}(n^2)$