Język w NSPACE (O (n)) i najprawdopodobniej nie w DSPACE (O (n))

Właściwie odkryłem, że zestaw języków kontekstowych, ( zaakceptowane języki) nie są tak szeroko omawiane, jak (zwykłe języki) lub (języki bezkontekstowe). A także problem otwarty nie jest tak znany jak problem „analogiczny”: „ ".$\mathbf{CSL}$$\mathbf{=NSPACE(O(n)) = LBA}$$\mathbf{REG}$$\mathbf{CFL}$$\mathbf{DSPACE(O(n))} =^{?} \mathbf{NSPACE(O(n))}$$\mathbf{P} =^{?} \mathbf{NP}$

Czy istnieje naprawdę taka analogia :?

1. Czy istnieje język w którego nie można udowodnić w (jak kompletne języki )?$\mathbf{CSL}$$\mathbf{DSPACE(O(n))}$$\mathbf{NP}$
2. Ponadto: Czy istnieje język w który jest „kompletny” w tym sensie: jeśli możemy udowodnić, że jest w , otrzymujemy ten ?$L$$\mathbf{CSL}$$L$$\mathbf{DSPACE(O(n))}$$\mathbf{DSPACE(O(n)) = NSPACE(O(n))}$
3. (Może to tylko kwestia opinii) Czy oba problemy są na tym samym poziomie trudności?

Bardziej znaną wersją tych pytań jest pytanie . Jeśli to (nieco trudny) argument wypełniający pokazuje, że , a więc oznacza dobrze znaną hipotezę .$\mathsf{L} \stackrel?= \mathsf{NL}$$\mathsf{L} = \mathsf{NL}$$\mathsf{DSPACE}(n) = \mathsf{NSPACE}(n)$$\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$$\mathsf{L} \neq \mathsf{NL}$

Przypuszczenie jest uważane (przez niektórych) za bardziej przystępne niż przypuszczenie . Nie jestem pewien, czy wiele osób ma opinię na temat hipotezy .$\mathsf{L} \neq \mathsf{NL}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$

Większy obraz dotyczy tego, czy twierdzenie Savitcha , które stwierdza, że dla uzasadnionego , jest ciasne. Chociaż , myślę, że większość ludzi uważa, że . Z drugiej strony nie jestem pewien, czy ludzie wierzą, że jest optymalnym powiększeniem; być może mniejszy wykładnik również działa, przynajmniej w niektórych przypadkach. Zobacz na przykład niedawny artykuł arXiv , Sparametryzowana złożoność przestrzeni logiki zmiennej pierwszego rzędu ograniczonej sprawdzaniem modelu , autorstwa Yijia Chen, Michaela Elberfelda i Moritza Müllera.$\mathsf{NSPACE}(t(n)) \subseteq \mathsf{DSPACE}(t(n)^2)$$t(n) \geq \log n$$\mathsf{NPSPACE} = \mathsf{PSPACE}$$\mathsf{NSPACE}(n^k) \neq \mathsf{DSPACE}(n^k)$$t(n)^2$

1. Tak, istnieją pełne języki CSL w ramach redukcji DSPACE (O (n)) . Zasadniczo nadal wariant ukierunkowanej osiągalności, który można ograniczyć do acyklicznej osiągalności, jeśli jest to pożądane.
2. Tak, patrz 1.

3. Masz na myśli, czy pytanie DSPACE (O (n)) = ^? NSPACE (O (n)) na tym samym poziomie trudności, co pytanie P = ^? NP ? Mamy dobre powody, by sądzić, że P jest ścisłym podzbiorem NP , ale nie jestem świadomy podobnie dobrze opracowanych powodów, by sądzić, że DSPACE (O (n)) jest ścisłym podzbiorem NSPACE (O (n)) . Pozwól, że skupię się na łatwiejszym pytaniu . Losowe spacery nie są „złe” do badania (pod względem osiągalności) niekierowanych wykresów związanych z SL$\mathsf{L} \stackrel?= \mathsf{NL}$. Oczywisty, trywialny analogiczny losowy spacer po ukierunkowanym wykresie źle zawiedzie w badaniu ukierunkowanego wykresu (w odniesieniu do osiągalności). Ale może istnieją inne podobne losowe sposoby eksploracji ukierunkowanego wykresu (lub warstwowego wykresu acyklicznego). Opierając się na twierdzeniu Savitcha, zgaduję nawet, że istnieją takie sposoby, jeśli chcemy zapisać zmienny zestaw pozycji na kierowanym wykresie podczas losowego procesu eksploracji. A potem wyzwaniem byłoby zrozumienie, czy zapisanie mniejszej liczby pozycji niż nie pozwoli na dobrą, losową eksplorację.$O(\log n)$$O(\log n)$

   Nawet po zrozumieniu, czy powinniśmy wierzyć , udowodnienie, że prawdopodobnie będzie tak samo niemożliwe, jak udowodnienie . Ryan Williams podaje jeden wyraźny powód i mówi:$\mathsf{L} \neq \mathsf{NL}$$\mathsf{P} \neq \mathsf{NP}$

   Poza tym nie znam żadnego szczególnego powodu, by sądzić, że „trudno jest udowodnić” poza spostrzeżeniem, że wiele osób próbowało i nikomu jeszcze się nie udało.

   odpowiedzieć Czy ALogTime! = PH jest trudny do udowodnienia (i nieznany)? Lance Fortnow w zasadzie poruszył to pytanie i nadal się nie zgadza. Moja lekcja brzmiała:

   Oznacza to, że stwierdzenie „ALogTime! = PH” jest dokładnie miejscem, w którym zaczynają się trudności w udowodnieniu wyników separacji. Można zauważyć, że to stwierdzenie jest faktycznie równoważne z „ALogTime! = NP”, ponieważ „ALogTime = NP” oznacza „P = NP = PH”.

Dodając do innych odpowiedzi, istnieje pojęcie redukowalności i kompletności dla problemu CSL vs. DCSL, mianowicie redukcja log-lin, i istnieją dość naturalne problemy z kompletnością CSL. Na przykład problem nierówności dla wyrażeń regularnych. Oto bardzo podobne pytanie do ciebie, wraz z odpowiedzią zawierającą dalsze informacje i odniesienia: /cstheory/1905/completeness-and-context-sensitive-languages

$SAT$ jest w . Przy założeniu , wówczas jest ściśle zawarty w ponieważ możemy przekształcić wielomianowe redukcje czasu w logarytmiczne redukcje przestrzeni, a jest zamknięty pod logarytmicznymi redukcjami przestrzeni. Nie są równe ze względu na twierdzenie o hierarchii. Jednak gdy to w wyniku zastosowania argumentu dopełniania. Ponieważ gdy wówczas jest ściśle zawarty w . Jednak i tym samym$NTIME(n) \subseteq DSPACE(n)$$L = P$$NP$$DSPACE(n)$$DSPACE(n)$$L = NL$$DSPACE(n) = NSPACE(n)$$L = NL$$L = P$$NP$$NSPACE(n)$$CSL = NSPACE(n)$$CSL \neq NP$ , a więc nie może być tak, że pewne problemem jest ponieważ implikuje to sprzeczność z , które otrzymuje się po założeniu .$CSL-complete$$NP$$CSL \neq NP$$L = P$

Ponadto można tu zobaczyć możliwą próbę udowodnienia :$L = P$

https://hal.archives-ouvertes.fr/hal-01999029