Oddzielanie przestrzeni logicznej od czasu wielomianowego

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 ≠ $L$$P$$L$$P$$NL$$LogCFL$$NC^i$$SAC^i$$AC^i$$SC^i$$L \neq P$

W jednym z moich blogach wspominałem dwa podejścia (wraz z odpowiadającymi im przypuszczeń) w kierunku udowodnienia $L \neq P$ . 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$ .

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.$\log^2(n)$$\mathsf P$$\mathsf P$$\mathsf L$

[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 P ≠ L ). 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.$\mathsf{P} \neq \mathsf{NC}$$\mathsf{P} \neq \mathsf{L}$

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 $L$$n$$L(n)$$\mathbb{Z}^{k(n)}$$k(n) = \Theta(n^2)$$B(a,n)$$\mathbb{Z}^{k(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 → x ∈ B ( a $an$$f(x_1, \dotsc, x_k)$$f$$L(n)$$B(a,n)$$L(n) \cap B(a,n)$ takie, że f ( → x ) = 1 .$\vec{x} \in B(a,n)$$f(\vec{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 P ≠ $L(n)$$B(a,n)$$\det(M(\vec{x}))$$M$$\leq 2^{n/d}$$x_1, \dotsc, x_k$$a < 1/(2d)$ .$\mathsf{P} \neq \mathsf{NC}$

Kluczowy jest tutaj związek między bitem a rozmiarem 2 n / d . W tym samym artykule pokazał:$an$$2^{n/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ć P ≠ N C jak w powyżej stanowiska (rzeczywiście, [1, propan, 7,5] konstruuje wielomianu$\neq$$\mathbb{R}$$\mathsf{P} \neq \mathsf{NC}$ 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.$g$$\det$$g$$\det$

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

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

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 $c_1$$c_2$$k$$k$$c_1 k \log(n)$$c_2 k \log(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 wn$o \left( \frac{n}{\log(n) \log(\log(n))} \right)$$f(k) = o(k)$$k$$k$$n^{f(k)}$$c$$k$$k$$n^c$ czas, wtedy P nie zawiera żadnej klasy złożoności przestrzeni większej niż NL.