Jakie są konsekwencje

46

Wiemy, że LNLP i że LNLL2 polyL , gdzie L2=DSPACE(log2n) . Wiadomo również, że polyLPponieważ ten drugi ma całkowite problemy w przestrzeni logarytmicznej, wielokrotne redukcje jeden-jedynki, podczas gdy ten drugi nie (ze względu na twierdzenie o hierarchii przestrzeni). W celu zrozumienia zależności między polyL i P , może pomóc zrozumieć najpierw związek pomiędzy L2 i P .

Jakie są konsekwencje L2P ?

Co z silniejszym L.kP. dla k>2) lub słabszym L.1+ϵP. dla ϵ>0 ?

argentpepper
źródło
4
@OrMeir Niedawno dodałem wyjaśnienie tego faktu do artykułu Wikipedii dotyczącego poliL .
argentpepper
13
Myślę, że następujące konsekwencje są oczywiste, a zwłaszcza nie zaskakujące: L.2)P. implikuje, że L.P. , ponieważ w przeciwnym razie byłoby to sprzeczne z hierarchią przestrzeni L.L.2) .
Sajin Koroth,
12
Dobre pytanie! Myślę, że to zdecydowanie warte nagrody. Przy okazji, tutaj jest prosta obserwacja, jeśli L.2)P. , to reS.P.ZAdomi(n)reT.jaM.mi(2)O(n)). Dlatego mamy bardziej wydajny algorytm dla CNF-SAT i odrzucamy ETH (hipoteza wykładnicza czasu).
Michael Wehar
3
Po komentarzu @ MichaelWehar, implikacja wynika ze standardowego argumentu wypełniającego, który rozciąga się na słabsze hipotezy: jeśli jest w P , to każdy problem, który można rozwiązać w przestrzeni liniowej (w tym problem satysfakcji), można rozwiązać w czasie 2 O ( n 1L.1+ϵP.. 2)O(n11+ϵ)
argentpepper
3
@SajinKoroth: Myślę, że twój komentarz, a także kontynuacja Michaela Wehara (i argentpeppera) powinny być odpowiedziami ...
Joshua Grochow

Odpowiedzi:

26

Oczywistą konsekwencją jest: implikuje LP, a zatem LPL.1+ϵP.LPLP .

Według twierdzenia o hierarchii przestrzeni . Jeśli L 1 + εP następnie LL 1 + εP .ϵ>0:LL1+ϵL1+ϵPLL1+ϵP.

Sajin Koroth
źródło
Mały przypis: Jeżeli , to mamy P N L lub N L L . P.L.P.N.L.N.L.L.
Michael Wehar,
27

obali hipotezęowykładniczym czasieL.2)P. .

Jeżeli to za pomocą argumentu wypełniającego D S P A C E ( n ) D T I M E ( 2 O ( L.2)P. . Oznacza to, że problem zadowalalnościSATDSPACE(n) można rozwiązać w2o(n)reS.P.ZAdomi(n)reT.jaM.mi(2)O(n))S.ZAT.reS.P.ZAdomi(n)2)o(n) krokach, obalając hipotezę o wykładniczym czasie.

Bardziej ogólnie, dla k 1 oznacza S TD S P C e ( n ) D T I M E ( 2 O ( N 1reS.P.ZAdomi(logkn)P.k1.S.ZAT.reS.P.ZAdomi(n)reT.jaM.mi(2)O(n1k))

(Ta odpowiedź została rozwinięta z komentarza @MichaelWehar.)

argentpepper
źródło
Dziękujemy za rozwinięcie komentarza! Doceniam to. :)
Michael Wehar,
1
Ponadto ostatnia hipoteza sugeruje również, że jest w DSPACE ( n ) DTIME ( 2 O ( n 1Qbfan). 2)O(n1k)
Michael Wehar,
8

Grupowy izomorfizm (z grupami podanymi jako tabliczki mnożenia) występowałby u P. Liptona, Snydera, a Zalcstein pokazał, że ten problem występuje w , ale nadal jest otwarte, czy występuje w P. Najlepszy obecnie górny limit to n O ( log n ) -czas, a ponieważ sprowadza się do izomorfizmu grafów, stanowi znaczącą przeszkodę dla umieszczenia wykresu iso w P.L.2)nO(logn)

Zastanawiam się, do jakich innych naturalnych i ważnych problemów miałoby to zastosowanie: to znaczy w ale z ich najlepiej znanym czasem quasi-wielomianem.L2

Joshua Grochow
źródło
1
Mówiąc dokładniej, bardziej ogólnym problemem quasi-grupowego izomorfizmu jest , który jest podklasą L 2 . β2)faOL.L.L.2)
argentpepper
1
Również problem rang grupy (biorąc pod uwagę skończoną grupę G jako tabliczkę mnożenia i liczbę całkowitą k , czy G ma zbiór generowania liczności k ?) Również ma tę właściwość. Algorytm jest tylko ponad podzbiorów G o liczności k ale używa dwóch istotnych faktów: (1) każda grupa skończonego ma prądotwórczego wielkości logarytmicznej oraz (2) członków podgrupy jest , która jest równa L . S.L.L.
argentpepper
1

Twierdzenie: Jeśli jakiegoś k > 2 , a P log ( C, F L ) i P N l .L.kP.k>2)P.log(dofaL.)P.N.L.

Załóżmy, że dla niektórych k > 2L.kP.k>2) .

Z „ Granic pamięci dla rozpoznawania języków bezkontekstowych i kontekstowych ” wiemy, że . Z twierdzenia o hierarchii przestrzeni wiemy, że D S P A C E ( log 2 ( n ) ) D S P A C E ( log k ( n ) ) .dofaL.reS.P.ZAdomi(log2)(n))reS.P.ZAdomi(log2)(n))reS.P.ZAdomi(logk(n))

Dlatego otrzymujemy log(dofaL.)reS.P.ZAdomi(log2)(n))reS.P.ZAdomi(logk(n))P. .

Również z twierdzenia Savitcha wiemy, że . Dlatego się N L D S P A C E ( log 2 ( n ) ) D S P C E ( log k ( n ) ) P .N.L.L.2)N.L.reS.P.ZAdomi(log2)(n))reS.P.ZAdomi(logk(n))P.

Michael Wehar
źródło