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”: „ ".
Czy istnieje naprawdę taka analogia :?
- Czy istnieje język w którego nie można udowodnić w (jak kompletne języki )?
- Ponadto: Czy istnieje język w który jest „kompletny” w tym sensie: jeśli możemy udowodnić, że jest w , otrzymujemy ten ?
- (Może to tylko kwestia opinii) Czy oba problemy są na tym samym poziomie trudności?
Odpowiedzi:
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ę .L.=?N L. L = N L. D S P A C E (n)= N S P A C E (n) D S P A C E (n)≠ N S P A C E (n) L ≠ N L
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 .L ≠ N L P ≠ N P D S P A C E (n)≠ N S P A C E (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.NSPACE(t(n))⊆DSPACE(t(n)2) t(n)≥logn NPSPACE=PSPACE NSPACE(nk)≠DSPACE(nk) t(n)2
źródło
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 SLL=?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(logn) O(logn)
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:L≠NL P≠NP
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:
źródło
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
źródło
Ponadto można tu zobaczyć możliwą próbę udowodnienia :L = P
https://hal.archives-ouvertes.fr/hal-01999029
źródło