Jaka jest domniemana zależność między językami P (PTime) i Type 1 (kontekstowymi)?

Nie wiadomo czy $P\subseteq CSL$ lub $P\not\subseteq CSL$, gdzie

• $P$ jest zbiorem wszystkich języków rozstrzygalnych w czasie wielomianowym na deterministycznej maszynie Turinga, oraz
• $CSL$ jest klasą języków kontekstowych, znanych jako równoważne $NSPACE(O(n))$ , języki ustalane przez automaty ograniczane liniowo.

W przypadku wielu otwartych pytań istnieje tendencja do jednej odpowiedzi ( la „większość ekspertów uważa, że $P\neq NP$ ”). Czy jest coś takiego dla tego pytania?

W szczególności, czy odpowiedź miałaby nieoczekiwane konsekwencje? Widzę tylko oczekiwane (ale niepotwierdzone) konsekwencje:

• Jeśli $P\subseteq CSL$ , to $P\subseteq NSPACE(O(n))\subsetneq NSPACE(O(n^2))$ (twierdzenie o hierarchii przestrzeni), stąd $P\subsetneq PSpace$ .
• Jeżeli $P\not\subseteq CSL$ , to jest język $l\in P\setminus NSPACE(O(n))$ , a zatem $l\in P\setminus NL$ , stąd $NL\subsetneq P$ .

(Potwierdzenie: drugą konsekwencję tych dwóch wskazał Yuval Filmus na /cs/69614/ )

Jeśli , to . Poprzez argument dopełniający implikuje to dla każdej dobrze zachowującej się funkcji wielomianowej i co . Uważam, że tak silna przewaga przestrzeni kosmicznej w czasie nie powinna być prawdą. Najbardziej znanym obecnie wynikiem w tym kierunku jest ze względu na Hopcroft, Paul i Valiant.$\mathrm{P\subseteq CSL}$$\mathrm{P\subseteq DSPACE}(n^2)$