Wyniki pokazujące istnienie / nieistnienie grafów skończonych o określonych właściwościach obliczeniowych implikują pewne wyniki złożoności

Czy są jakieś znane wyniki wskazujące, że istnienie (lub nieistnienie) grafów skończonych o określonych właściwościach obliczeniowych implikuje pewne wyniki złożoności (takie jak P = NP)?

Oto jeden całkowicie hipotetyczny wynik: jeśli istnieje skończony wykres z rozłożonymi krawędziami A, B, C i D, tak że wszystkie maksymalne dopasowania albo zawierają wszystkie A, B, C i D, albo nie zawierają żadnego z A, B, C i D , a następnie P = NP.

Jeden z wyników tego rodzaju udowodnił Lipton „Udowadniając, że wykres nie ma dużej kliki: związek z teorią Ramseya” . Łączy dolne granice przypuszczeń z czysto graficznymi wynikami teoretycznymi, pokazującymi, że jeśli$NP$ nie jest zawarte w $coNTIME(n^{O(\log n)})/(\log \log n)$, to niedopuszczalność $MAX-CLIQUE$sugeruje, że istnieją wykresy o czystych właściwościach teoretycznych Ramseya. (Zobacz definicje w artykule). Nie mam pojęcia, czy poczyniono postępy w udowodnieniu, czy takie wykresy rzeczywiście istnieją.

Przepraszam, natknąłem się na to 1-letnie pytanie dopiero teraz ...

W rzeczywistości istnieje wiele wyników wskazujących, że wyraźne wykresy z niektórymi właściwościami sugerują silne dolne granice funkcji boolowskich. Powiedzmy, że wykresy o wysokim powinowactwie lub rzucie wskazują na silne dolne granice dla formuł i programów rozgałęziających. Istnieją również „prostsze” miary wykresów, których dobre dolne granice miałyby wielkie konsekwencje w złożoności obliczeniowej. Pozwól mi naszkicować niektóre z nich.

Wyświetl wykresy jako zestawy krawędzi. Pozwolić$s(G)$ być najmniejszą liczbą $s$ takie, że $G$ może być napisane jako skrzyżowanie $\leq s$ wykresy, z których każdy jest związkiem $\leq s$bicliques (dwustronne pełne wykresy). Łatwe liczenie pokazuje to$s(G)\geq n^{1/2}$ dla prawie wszystkich dwustronnych $n\times n$wykresy. Ale według wyników Valiant, każdy wyraźny dwustronny wykres$G$ (a dokładniej sekwencja wykresów) z $s(G)\geq n^c$ na stałe $c>0$rozwiązałoby stary problem: dałoby funkcję boolowską, której nie można obliczyć za pomocą obwodu o głębokości logarytmicznej o rozmiarze liniowym. Przypuszcza się, że gęste wykresy bez$K_{2,2}$ mieć duże $s(G)$.

Jeszcze lepiej, niech $Star(G)$ być najmniejszą liczbą fanów$2$ operacje łączenia i przecinania wystarczające do wygenerowania $G$ zaczynając od pełnych gwiazd (wykresy typu $K_{1,n}$ lub $K_{n,1}$). Liczenie pokazuje, że większość wykresów ma$Star(G)=\Omega(n^2/\log n)$. Ale każdy$G$ z $Star(G)\geq (4+c)n$ na stałe $c>0$dałoby jawną funkcję logiczną wymagającą obwodów o wykładniczej wielkości! Jeśli wykres ma wymiar$m\times n$ z $m=o(n)$, a nawet dolną granicę $Star(G)\geq (2+c)n$miałby takie same konsekwencje. Jak dotąd możemy najlepiej pokazać$Star(G)\geq 2n-1$.

Pozwolić $Sym(G)$ być najmniejszą liczbą $t$ dla którego istnieje podzbiór $T\subseteq\{0,1,\ldots,t\}$ i sekwencja $t$ bicliques takie, że $(u,v)\in G$ iff liczba liczby zawierających $(u,v)$ należy do $T$. Ponownie liczenie daje$Sym(G)\geq n/2$dla większości wykresów. Ale według wyników Yao, Beigela i Tarui każdy wyraźny wykres z$Sym(G)$ większy niż $2^{poly(\ln\ln n)}$ dałby nam funkcję boolowską na zewnątrz $ACC$. Ostrzeżenie: samo bycie „skomplikowanym kombinatorycznie” nie oznacza dużego$Sym(G)$: istnieją silnie wykresy Ramseya, dla których $Sym(G)=O(\log n)$, nawet jeśli $T$ = zestaw nieparzystych liczb całkowitych.

Więcej informacji na temat tego, jak to wszystko się dzieje, można znaleźć tutaj .

Klasycznym przykładem jest Valiant (nie znam odnośnika, ale myślę, że jest to opisane w książce Hoory, Linial i Wigderson o grafach ekspanderów ). Valiant pokazał wyraźną dolną granicę (myślę, że pewna wyraźna funkcja$f:{0,1}^n\rightarrow {0,1}^n$ nie ma obwodu $O(n)$ rozmiar i $O(\log n)$głębokość - coś, czego wciąż jesteśmy daleki od udowodnienia) przy założeniu, że pewne typy wykresów, zwane superkoncentratorami, nie istnieją. (Było to pytanie asymptotyczne i nie dotyczyło tylko jednego wykresu.) Później jednak wykazał, że one istnieją (i w rzeczywistości mają inne zastosowania)

Odpowiedź z pewnością brzmi „tak”, jeśli mówimy o rodzinach grafów, a nie o konkretnych grafach. Na przykład istnieje przypuszczenie Mihaila i Vazirani, że wszystkie wykresy politopalne 0/1 są albo dobrymi, albo bardzo dobrymi ekspansjami krawędzi (tj. Że ich ekspansja krawędzi jest ograniczona przez 1 / wielomian (stopień) lub 1).

Jeśli to prawda, istnieją skuteczne algorytmy przybliżenia Monte Carlo z randomizowanym łańcuchem Markowa dla szeregu otwartych problemów kombinatorycznych i zliczających za pomocą strategii próbkowania Alona, ​​Jerruma i Sinclaira.

Podobnie, jeśli istnieją rodziny wykresów wielopłatowych, których średnica rośnie szybciej niż jakikolwiek wielomian pod względem liczby aspektów i stopnia wykresu, wówczas programowania liniowego nie można rozwiązać w silnie wielomianowym czasie za pomocą algorytmów podążających za krawędzią.

Rozszerzając komentarz Ananda Kulkarniego:

Załóżmy, że istnieje deterministyczna maszyna Turinga M, która rozpoznaje SAT w czasie wielomianowym. Wtedy skończona relacja przejścia M będzie funkcją. Znamy TM, które rozpoznają SAT w czasie wielomianowym, ale ich relacje przejściowe nie są funkcjami. Zwróć uwagę, że relacja przejścia jest dwudzielnym grafem z krotkami (stan, symbol taśmy) w jednej dwuczęściowej, krotkami (stan, symbol taśmy, ruch) w drugiej dwuczęściowej i łukami od par do potrójnych.

Tak trywialnie, jeśli istnieje taki digraf, który jest funkcją, to P = NP.

Oczywiście nie jest to bardzo naturalna definicja, ponieważ wymaga maszynerii pomocniczej, aby nadać sens wymogowi, że każda ścieżka w przestrzeni stanu, która osiąga stan akceptacji, ma długość ograniczoną wielomianem wielkości wejściowej. Nie jest wcale oczywiste, jak wygląda zestaw skończonych grafów reprezentujących maszyny Turinga związane z czasem politycznym, ani czy te wykresy mają interesujące właściwości teoretyczne.