Trudne do rozwiązania podkluczowe problemy z grafem twardym

25

W świetle ostatnich wyników Arory , Baraka i Steurera , Subexponential Algorytmy dla unikalnych gier i powiązanych problemów , interesują mnie problemy z grafem, które mają algorytmy czasu podwykładniczego, ale uważam, że nie jest to rozwiązanie wielomianowe. Znanym przykładem jest izomorfizm grafów, który ma algorytm subklonencjalny . Innym przykładem jest problem log-Clique, który można rozwiązać w quasi-wielomianowym czasie ( ). $2^{O(n^{1/2} \log n)}$ $n^{O(\log n)}$

Szukam interesujących przykładów i najlepiej odniesienia do ankiet na temat podwykładniczych problemów z twardym grafem (niekoniecznie zupełnych). Ponadto, czy są jakieś problemy z wykresem niekompletnym z algorytmami subwykładniczego czasu? $NP$ $NP$

Impagliazzo, Paturi i Zane wykazali, że hipoteza czasu wykładniczego implikuje, że klikanie, k-kolorowalność i pokrycie wierzchołków potrzebują czasu. $2^{\Omega(n)}$

cc.complexity-theory reference-request

— Mohammad Al-Turkistany
źródło

2

Dla kompletności: log-CLIQUE =

{(G, k) | G has n vertices, k = \log n and G has a clique of size k}

$\{(G, k) | G \text{ has }n\text{ vertices, }k = \log n\text{ and }G\text{ has a clique of size }k\}$

— MS Dousti

20

Nawiasem mówiąc, problem Max Clique, w całości, można rozwiązać w czasie gdziejest rozmiarem danych wejściowych. $2^{\tilde O(\sqrt N)}$ $N$

Jest to trywialne, jeśli wykres jest reprezentowany przez macierz przylegania, ponieważ wtedy , a szukanie brutalnej siły zajmie czas . $N=|V|^2$ $2^{O(|V|)}$

Ale możemy uzyskać tę samą granicę, nawet jeśli wykres jest reprezentowany przez listy przyległości, za pomocą algorytmu czasu działania . Aby zobaczyć jak, zdobądźmy $2^{\tilde O(\sqrt{|V| + |E|})}$ -Time algorytm dla NP-zupełny problemu decyzyjnego, w którym podano wykresii chcemy wiedzieć, czy istnieje klika rozmiaru. $2^{\tilde O(\sqrt{|V| + |E|})}$ $G=(V,E)$ $k$ $\geq k$

Algorytm po prostu usuwa wszystkie wierzchołki stopnia i zachodzące na nich krawędzie, a następnie robi to ponownie, i tak dalej, dopóki nie zostanie nam indukowany wierzchołkiem subgraph nad podzbiorem wierzchołków, każdy o stopniu , lub z pustym wykresem. W tym drugim przypadku wiemy, że nie może istnieć żadna klika o rozmiarze . W pierwszym przypadku przeprowadzamy wyszukiwanie siłowe z grubsza . Zauważ, że i $< k$ $V'$ $\geq k$ $\geq k$ $|V'|^k$ $|E| \geq k\cdot |V'| /2$ , tak że , a więc poszukiwanie brute-force działa w czasie faktycznie działa w czasie $k\leq |V'|$ $|E| \geq k^2/2$ $|V'|^k$ . $2^{O(\sqrt{|E|} \cdot \log |V|)}$

— Luca Trevisan
źródło

12

Rzeczywiście, z tego rodzaju powodów Impagliazzo, Paturi i Zane argumentowali, że pytając o złożoność

vs

, musisz ustawić

aby była wielkością świadka (którą musisz zdefiniować w ramach problem). W przypadku kliki

świadek ma rozmiar

2^{Ω (n)}

$2^{\Omega(n)}$

2^{o (n)}

$2^{o(n)}$

n

$n$

k

$k$

dla małego

, podczas gdy, jak mówisz, możesz założyć, że wlog jest co najmniej

krawędzi i rozmiar wejściowy jest znacznie większy niż rozmiar świadka.

\log (\binom{| V |}{k}) \sim k \log | V |

$\log \binom{|V|}{k} \sim k\log |V|$

k

$k$

k | V |

$k|V|$

— Boaz Barak,

22

Ponieważ każdy płaski wykres na wierzchołkach ma szerokość $n$ wszystkie problemy, które można rozwiązać w czasiedla wykresów szerokości co najwyżej ~(istnieje wiele takich problemów) mają algorytmy czasu podwykładniczego na wykresach płaskich poprzez obliczenie współczynnika stałego aproksymacja do szerokości grzbietu w czasie wielomianowym (na przykład poprzez obliczenie szerokości gałęzi za pomocą algorytmu ratcatcher), a następnie uruchomienie algorytmu długości grzbietu, co daje czas działania postaci $O(\sqrt{n})$ $O^*(2^{O(k)})$ $k$ dla wykresów nawierzchołkach. Przykładami są Planarny zestaw niezależny i Planarny zestaw dominujący, które oczywiście są NP-kompletne. $O^*(2^{O(\sqrt{n})})$ $n$

— Bart Jansen
źródło

15

Istnieje ścisły związek między sub wykładniczym rozwiązaniem czasowym (SUBEPT) a ustaloną ciągliwością parametrów (FPT). Łącze między nimi podano w poniższym artykule.

Izomorfizm między podwykładniczą i sparametryzowaną teorią złożoności , Yijia Chen i Martin Grohe, 2006.

W skrócie, wprowadzili pojęcie zwane mapowaniem miniaturyzacji , które mapuje sparametryzowany problem na inny sparametryzowany problem . Widząc normalny problem jako problem sparametryzowany przez rozmiar wejściowy, mamy następujące połączenie. (Zobacz twierdzenie 16 w pracy) $(P,\nu)$ $(Q,\kappa)$

Twierdzenie . jest w SUBEPT iff jest w FPT. $(P,\nu)$ $(Q,\kappa)$

Uważaj na definicje tutaj. Zwykle patrzymy na problem kliki sparametryzowany w , więc nie ma algorytmu sub-wykładniczego czasu, który zakłada hipotezę wykładniczego czasu. Ale tutaj pozwalamy sparametryzować problem na podstawie wielkości wejściowej , dlatego problem można rozwiązać za pomocą $k$ $k$ $O(m+n)$ , który jest sub wykładniczym algorytmem czasu. Twierdzenie to mówi nam, żeproblem klikijest stałym parametrem możliwym do przełknięcia pod pewnym skrętem parametru, co jest rozsądne. $2^{O(\sqrt{m}\log m)}$ $k$ $k$

Ogólnie rzecz biorąc, problemy w SUBEPT w ramach redukcji SERF (rodziny redukcji sub wykładniczej) mogą zostać przekształcone w problemy w FPT w ramach redukcji FPT. (Twierdzenie 20 w pracy) Ponadto połączenia są jeszcze silniejsze, ponieważ dostarczyły one twierdzenia o izomorfizmie między całą hierarchią problemów w wykładniczej teorii złożoności czasowej i sparametryzowanej teorii złożoności. (Twierdzenie 25 i 47) Chociaż izomorfizm nie jest kompletny (między nimi brakuje pewnych powiązań), dobrze jest mieć jasny obraz tych problemów, a my możemy badać algorytmy sub-wykładnicze za pomocą sparametryzowanej złożoności.

Aby uzyskać więcej informacji, zobacz ankietę Jörga Fluma i Martina Grohe oraz redaktora kolumny złożoności Jacobo Torána.

— Hsien-Chih Chang 張顯之
źródło

Tak. btw, Flum i Grohe napisali ankietę; Toran jest edytorem kolumny złożoności.

— Andy Drucker,

@Andy: Dziękujemy za korektę. Zmienię odpowiednio artykuł.

— Hsien-Chih Chang 之之

12

innym przykładem może być gra Cop i Robber, która jest trudna do pokonania, ale można ją rozwiązać w czasie na wykresach z n wierzchołkami. Zapis bibliograficzny BibTeX w XML Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, Karol Suchan: Ściganie szybkiego rabusia na wykresie. Teoria Comput. Sci. 411 (7-9): 1167-1181 (2010) $2^{o(n)}$

— XXYYXX
źródło

3

Ups, to może być haniebne, ale od dawna wierzyłem, że problemy twarde

nie mają algorytmów subwykładniczych, tylko dlatego, że hipoteza o wykładniczym czasie. :(

N P

$\mathsf{NP}$

— Hsien-Chih Chang 張顯之

6

Nie wstyd ... ale jeden prosty sposób, aby zobaczyć to nieprawda jest do podjęcia wszelkich

języka -hard

, a następnie tworząc „wyściełany” wersja

, w którym wystąpienia „tak” mają postać

, przy czym

, dla niektórych stałych

. Zatem

oznacza

N P

$NP$

L \in N P T I M E (n^{k})

$L \in NPTIME(n^k)$

L^{'}

$L'$

(x, 1^{| x |^{c}})

$(x, 1^{|x|^c})$

x \in L

$x \in L$

c > k

$c > k$

L^{'}

$L'$

N P

$NP$ , ale ma deterministyczny algorytm działający w czasie zasadniczo

.

2^{n^{k / c}}

$2^{n^{k/c}}$

— Andy Drucker,

7

Najlepszy algorytm aproksymacji dla kliki daje niewiarygodnie zły współczynnik aproksymacji (należy pamiętać, że współczynnik aproksymacji jest trywialny). $n/\text{polylog } n$ $n$

Istnieją twardości wyników aproksymacji przy różnych założeniach twardości, które nie do końca pasują do tego, ale wciąż dają twardość . Osobiście uważam, że przybliżenie dla kliki jest tak dobre, jak by to zrobiły algorytmy wielomianowe. $n^{1-o(1)}$ $n/\text{polylog } n$

Ale przybliżenie dla kliki można łatwo wykonać w czasie quasi-wielomianowym. $n/\text{polylog } n$

Problem trudny dla NP to problem, który ma redukcję czasu wielomianowego względem SAT. Nawet jeśli SAT potrzebuje czasu , może to przełożyć się na czas dla problemu, do którego redukujemy. Jeśli ten ostatni ma wielkość wejściową N, może się zdarzyć, że dla małej stałej . $2^{\Omega(n)}$ $2^{\Omega(N^\epsilon)}$ $N=n^{1/\epsilon}$ $\epsilon$

— Dana Moshkovitz
źródło