Oddzielanie przestrzeni logicznej od czasu wielomianowego

24

Oczywiste jest, że każdy problem, który można rozstrzygnąć w deterministycznej przestrzeni logów ( ), występuje co najwyżej w czasie wielomianowym ( ). Tam jest wiele klas złożoności między i . Przykłady obejmują , , , , , . Uważa się, że .P L P N L L o g C F L N C i S A C i A C i S C i L PLPLPNLLogCFLNCiSACiACiSCiLP

W jednym z moich blogach wspominałem dwa podejścia (wraz z odpowiadającymi im przypuszczeń) w kierunku udowodnienia LP . Oba te podejścia opierają się na programach rozgałęziających i dzieli ich 20 lat !! Są inne sposoby i / lub przypuszczenia kierunku oddzielania L z P (OR) oddzielające wszystkie klasy pośredniej między L i P .

Shiva Kintali
źródło
myślę, że ten problem kompresji sekwencji przebiegu TM jest związany
vzn

Odpowiedzi:

21

Głębokość obwód dolne granice (równoważnie, rozmiar wzoru dolne granice) są prawdopodobnie najbardziej naturalne podejścia: a super- głębokość dolna granica dla problem w P by oddzielić P z L i techniki komunikacji złożoność Karchmer-Wigderson może bądź do tego naturalny.log2(n)PPL

Noam
źródło
3
Czy przeszkody z dowodem naturalnym nie byłyby tutaj problemem? Jestem ciekawy, dlaczego tak by było.
Suresh Venkat
6
Tak, zdecydowanie wydaje się, że taki dowód musiałby być „nienaturalny”, ale o ile rozumiem, musiałyby być inne podejścia wymienione w poście na blogu.
Noam
8

[1] udowadnia dolną granicę dla przypadków przepływu minimalnego kosztu, którego rozmiary bitów są wystarczająco duże (ale wciąż liniowe) w porównaniu z rozmiarem wykresu, a ponadto udowodnił, że jeśli można wykazać tę samą dolną granicę dla danych wejściowych o wystarczająco małych wartościach rozmiar bitu oznaczałoby (a zatem PL ). Jest to, na wysokim poziomie, to samo, co odpowiedź Noama, ponieważ chodzi o udowodnienie dolnych granic głębokości obwodu (= dolne granice wielkości formuły), ale wydaje się, że jest to zupełnie inny kierunek niż gry Karchmer-Wigderson.PNCPL

Bardziej szczegółowo [1] pokazuje, co następuje. Używając tego samego zapisu, co w artykule, niech oznacza język przepływu mincost. Możemy myśleć o języku przepływu mincost na wykresach n -vertex, oznaczonym L ( n ) , jako podzbiór Z k ( n ) dla niektórych k ( n ) = Θ ( n 2 ) , z liczbami całkowitymi kodowanymi przez ciągi bitów . Niech B ( a , n ) oznacza zbiór wszystkich wektorów w Z k ( n )LnL(n)Zk(n)k(n)=Θ(n2)B(a,n)Zk(n)gdzie współrzędnych każdej liczby całkowitej bitowy rozmiarze co najwyżej . Biorąc pod uwagę funkcję f ( x 1 , , x k ) (określimy, jaki rodzaj funkcji później), mówimy, że f oddziela L ( n ) w obrębie B ( a , n ), jeśli punkty w L ( n ) B ( a , n ) są dokładnie tymi xB ( a ,anf(x1,,xk)fL(n)B(a,n)L(n)B(a,n) takie, że f ( x ) = 1 .xB(a,n)f(x)=1

Twierdzenie [1, Twierdzenie 7.3] Jeżeli jest oddzielone w B ( a , n ) przez det ( M ( x ) ), gdzie M jest macierzą wielkości 2 n / d, której zapisy są (złożone) kombinacje liniowe z x 1 , , x k , i takie, że a < 1 / ( 2 d ) , to PNL(n)B(a,n)det(M(x))M2n/dx1,,xka<1/(2d) .PNC

Kluczowy jest tutaj związek między bitem a rozmiarem 2 n / d . W tym samym artykule pokazał:an2n/d

Twierdzenie [1, Twierdzenie 7.4] Hipoteza powyższego zdania dotyczy wszystkich wystarczająco dużych granic bitów .a

Dowód powyższego twierdzenia używa niektórych ciężkich młotów jako czarnych skrzynek, ale poza tym jest elementarny (uwaga: „elementarny” łatwy ”). Mianowicie, wykorzystuje on Milnor-Thom związany z liczbą połączonych komponentów prawdziwej odmiany semialgebraicznej (ta sama granica stosowana przez Ben-Or w celu udowodnienia niższych granic odrębności / sortowania elementów w modelu drzewa obliczeń rzeczywistych), rozkład Collinsa ( używane do udowodnienia skutecznej eliminacji kwantyfikatora w stosunku do R ), ogólnego argumentu pozycji i kilku innych pomysłów. Jednakże, wszystkie te techniki tylko zależy od stopnia wielomianów dotyczy, a więc nie może być stosowany, aby udowodnić PN C jak w powyżej stanowiska (rzeczywiście, [1, propan, 7,5] konstruuje wielomianuRPNC w takim samym stopniu jak det, tak że powyższa propozycja zawodzi, g zamiast det ). Analiza tej sytuacji i poszukiwanie właściwości wykraczających poza stopień była jedną z inspiracji dla GCT.gdetgdet

[1] K. Mulmuley. Dolne granice w modelu równoległym bez operacji bitowych . SIAM J. Comput., 28 (4), 1460–1509, 1999

Joshua Grochow
źródło
8

To sprawiło, że mój dzień, kiedy mój przyjaciel James powiedział mi, że ten wątek sprzed lat został ponownie rozpalony. Dziękuję za to.

Miałem też ochotę udostępnić kilka interesujących referencji dotyczących L vs Log (DCFL) vs Log (CFL). Miłego dnia!

http://link.springer.com/chapter/10.1007%2F978-3-642-14031-0_35#page-1

http://link.springer.com/chapter/10.1007/3-540-10003-2_89?no-access=true

http://link.springer.com/chapter/10.1007%2F978-3-642-00982-2_42#page-1

http://www.researchgate.net/publication/220115950_A_Hardest_Language_Recognized_by_Two-Way_Nondeterministic_Pushdown_Automata

Michael Wehar
źródło
7

ten nowy artykuł został właśnie podkreślony przez Lucę Aceto na swoim blogu jako najlepszy artykuł studencki EATCS na ICALP 2014 i ma nowatorski sposób oddzielenia NL / P:

  • Wyniki twardości dla skrzyżowania Non-pustka Wehar

    Dokładnie analizujemy konstrukcję Karakostasa, Liptona i Viglasa (2003), aby pokazać, że problem braku pustki przecięcia dla DFA (deterministyczne automaty skończone) charakteryzuje klasę złożoności NL. W szczególności, jeżeli ograniczone do binarnych taśmy pracy alfabetu, to istnieje stałe i c 2 , że dla każdego k przecięcia nie-pustki o k DFA jest rozpuszczalny w c 1 k log ( n ) przestrzeni, ale nie jest rozpuszczalny w c 2 k log ( n )c1c2kkc1klog(n)c2klog(n)przestrzeń. Optymalizujemy konstrukcję, aby pokazać, że dla dowolnej liczby skrzyżowań DFA brak pustki nie jest do rozwiązania w space. Ponadto, jeśli istnieje funkcjaf(k)=o(k)taka, że ​​dla każdegokskrzyżowania niepustość dlak DFA jest rozwiązywalna w czasienf(k), to P ≠ NL. Jeżeli nie istnieje stała ctaka, że ​​dla każdegokskrzyżowania nie pustka dlakDFA jest rozwiązywalna wnco(nlog(n)log(log(n)))f(k)=o(k)kknf(k)ckknc czas, wtedy P nie zawiera żadnej klasy złożoności przestrzeni większej niż NL.

vzn
źródło