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

10

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”: „ ".doS.L.=N.S.P.ZAdomi(O(n))=L.bZARmisoldofaL.reS.P.ZAdomi(O(n))=?N.S.P.ZAdomi(O(n))P.=?N.P.

Czy istnieje naprawdę taka analogia :?

  1. Czy istnieje język w którego nie można udowodnić w (jak kompletne języki )?doS.L.reS.P.ZAdomi(O(n))N.P.
  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.doS.L.L.reS.P.ZAdomi(O(n))reS.P.ZAdomi(O(n))=N.S.P.ZAdomi(O(n))
  3. (Może to tylko kwestia opinii) Czy oba problemy są na tym samym poziomie trudności?
rl1
źródło
L. vs. jest bardziej analogicznym problemem niż vs. . N.L.P.N.P.
rus9384
Myślę, że otrzymałeś wystarczająco dobre odpowiedzi; możesz je zaakceptować. Jeśli ci dwaj odpowiadający nie wiedzą, pytanie jest prawdopodobnie otwarte. Jeśli uważasz, że to jest pomocne, możesz ponownie napisać post na temat informatyki teoretycznej , ale pamiętaj, aby zamieścić link tutaj, aby ludzie nie marnowali czasu na pisanie tych samych rzeczy.
Raphael

Odpowiedzi:

8

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.reS.P.ZAdomi(n)=N.S.P.ZAdomi(n)reS.P.ZAdomi(n)N.S.P.ZAdomi(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.reS.P.ZAdomi(n)N.S.P.ZAdomi(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)lognNPSPACE=PSPACENSPACE(nk)DSPACE(nk)t(n)2)

Yuval Filmus
źródło
Pomaga to zobaczyć powiązane problemy. Dziękuję za to.
rl1
Powiedziałeś: „Nie jestem pewien, czy wiele osób ma opinię na temat hipotezy ." Ale przypuszczenie jest wciąż przedmiotem badań, prawda? DSPACE(n)NSPACE(n)
rl1
Jeśli masz przez to na myśli przedmiot aktywnych badań, nie jestem pewien. Ale z pewnością będzie interesujące (dla społeczności) znać odpowiedź.
Yuval Filmus
Dlaczego argumentowanie dopełnienia jest trudne? Jeśli nie oznacza, że ​​DTM potrzebuje przestrzeni do symulacji NTM? L=NLO(logn)
rus9384
@ rus9384 Spróbuj uruchomić argument, aby zobaczyć trudność, lub spójrz na link.
Yuval Filmus,
1
  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 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:LNLPNP

    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”.

Thomas Klimpel
źródło
Dzięki! Odpowiadałoby to na wszystkie moje pytania, ale nie rozumiem twojej odpowiedzi. 1. Łączność (osiągalność) w grafach ukierunkowanych to problem - kompletny ( NL-complete ). Czy mógłbyś więc wyjaśnić „wariant”, który masz na myśli (lub podać link)? NL
rl1
@ rl1 Kodowanie kierowanego wykresu jest inne, a zwłaszcza jego rozmiar to O (exp (n)). Zasadniczo wykres przejścia odpowiedniej maszyny Turinga (ze stałym limitem pamięci).
Thomas Klimpel
Czy masz link do dokładnej definicji swojego wariantu i dowodu „kompletności”?
rl1
@ rl1 Sprawdziłem kilka wprowadzających teorii teorii złożoności. Traktowanie tego tematu w Papadimitriou jest dobre i szczegółowe, leczenie w Arora / Barak jest również wystarczająco dobre. Mniej pewny, czy leczenie w Sipser lub Goldreich da ci to, czego chcesz. Papadimitriou ma również sens, ponieważ jest to starsza książka i jest to starszy temat, a także temat kodowania grafów przejściowych przez odpowiednio ograniczone maszyny Turinga również pojawia się w nowszych badaniach Papadimitriou.
Thomas Klimpel,
Papadimitriou (Computational Complexity, 1995) podaje ćwiczenie, że (s. 67) i twierdzenie, że „REACHABILITY jest -kompletny (s. 398). Ale to nie odpowiada na moje pytania, więc niestety nie mogłem znaleźć rezultatu, o którym wspomniałeś w swojej odpowiedzi w 1. i 2.CSL=NSPACE(n)NL
rl1
1

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

Hermann Gruber
źródło
-1

S.ZAT. 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 samymN.T.jaM.mi(n)reS.P.ZAdomi(n)L.=P.N.P.reS.P.ZAdomi(n)reS.P.ZAdomi(n)L.=N.L.reS.P.ZAdomi(n)=N.S.P.ZAdomi(n)L.=N.L.L.=P.N.P.N.S.P.ZAdomi(n)doS.L.=N.S.P.ZAdomi(n)doS.L.N.P. , 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 .doS.L.-doomplmitmiN.P.doS.L.N.P.L.=P.

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

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

Frank Vega
źródło