Algorytm holograficzny

Aby zapoznać się z przechowywaniem danych holograficznych (które nie jest powiązane), zobacz Przechowywanie danych holograficznych .

W informatyce algorytm holograficzny to algorytm wykorzystujący redukcję holograficzną. Redukcja holograficzna to redukcja w stałym czasie , która odwzorowuje fragmenty rozwiązania wiele do wielu, tak że suma fragmentów rozwiązania pozostaje niezmieniona. Koncepcje te zostały wprowadzone przez Leslie Valiant , który nazwał je holograficznymi , ponieważ „ich efekt można postrzegać jako wytwarzanie wzorców interferencji między fragmentami roztworu”. Algorytmy nie mają związku z holografią laserową , chyba że metaforycznie. Ich moc bierze się z wzajemnego anulowania wielu wkładów w sumę, analogicznie do wzorców interferencji w hologramie.

Algorytmy holograficzne zostały wykorzystane do znalezienia rozwiązań problemów w czasie wielomianowym bez takich wcześniej znanych rozwiązań dla specjalnych przypadków spełnialności , pokrycia wierzchołków i innych problemów grafowych . Zyskały one godne uwagi dzięki spekulacjom, że są istotne dla problemu P kontra NP i ich wpływu na teorię złożoności obliczeniowej . Chociaż niektóre problemy ogólne są #P-trudnymi problemami, rozwiązane przypadki specjalne same w sobie nie są #P-trudne, a zatem nie dowodzą, że FP = #P.

Algorytmy holograficzne mają pewne podobieństwa do obliczeń kwantowych , ale są całkowicie klasyczne.

Problemy z Holantem

Algorytmy holograficzne istnieją w kontekście problemów Holanta, które uogólniają liczenie problemów spełniania ograniczeń (#CSP). Instancja #CSP to hipergraf G =( V , E ) zwany wykresem ograniczeń . ${\ displaystyle f_ {v}.}$ hiperkrawędź reprezentuje zmienną, a każdy $wierzchołek$ ograniczenie Wierzchołek jest połączony z hiperkrawędzią, jeśli ograniczenie na wierzchołku obejmuje zmienną na hiperkrawędzi. Problem z liczeniem polega na obliczeniu

${\ Displaystyle \ suma _ {\ sigma: E \ do \ {0,1 \}} \ prod _{v\in V}f_{v}(\sigma |_{E(v)}),~~~~~~~~~~(1)}$

która jest sumą wszystkich przypisań zmiennych, iloczynem każdego ograniczenia, gdzie dane wejściowe do ograniczenia są zmiennymi na incydentalnych hiperkrawędziach $fa$$displaystyle v}$ .

Problem Holanta jest jak #CSP, z wyjątkiem tego, że dane wejściowe muszą być wykresem, a nie hipergrafem. Ograniczanie klasy grafów wejściowych w ten sposób jest rzeczywiście uogólnieniem. Biorąc pod uwagę instancję #CSP, zastąp każdą hiperkrawędź e o rozmiarze s wierzchołkiem v o stopniach s z krawędziami incydentnymi z wierzchołkami zawartymi w e . Ograniczeniem dla v jest funkcja równości arity s . To identyfikuje wszystkie zmienne na krawędziach incydentnych z v , co ma taki sam efekt jak pojedyncza zmienna na hiperkrawędzi e .

W kontekście problemów Holanta wyrażenie w (1) nazywane jest Holantem od powiązanej sumy wykładniczej wprowadzonej przez Valianta.

Redukcja holograficzna

Standardową techniką w teorii złożoności jest redukcja wielu-jeden , w której przykład jednego problemu jest redukowany do wystąpienia innego (miejmy nadzieję, prostszego) problemu. Jednak redukcje holograficzne między dwoma problemami obliczeniowymi zachowują sumę rozwiązań, niekoniecznie zachowując zgodność między rozwiązaniami. Na przykład całkowita liczba rozwiązań w obu zestawach może zostać zachowana, nawet jeśli poszczególne problemy nie mają pasujących rozwiązań. Sumę można również zważyć, zamiast po prostu zliczać liczbę rozwiązań, używając liniowych wektorów bazowych .

Ogólny przykład

Wygodnie jest rozważyć redukcje holograficzne na grafach dwudzielnych. Wykres ogólny można zawsze przekształcić w wykres dwudzielny, zachowując wartość Holanta. Odbywa się to poprzez zastąpienie każdej krawędzi w grafie ścieżką o długości 2, która jest również znana jako 2-stretch grafu. Aby zachować tę samą wartość Holanta, każdemu nowemu wierzchołkowi przypisuje się binarne ograniczenie równości.

Rozważmy wykres dwudzielny G = ( U , V , mi ) gdzie ograniczenie przypisane do każdego wierzchołka $displaystyle$ u $f_ {u}}$ a ograniczenie przypisane do każdego wierzchołka ${\ Displaystyle v \ w V}$ jest ${\ displaystyle f_ {v}}$ . ten problem z liczeniem przez ${\ Displaystyle {\ text {Holant}} (G, f_ {u}, f_ {v}).}$ Jeśli wierzchołki w U są postrzegane jako jeden duży wierzchołek stopnia | mi |, wtedy ograniczeniem tego wierzchołka jest iloczyn tensorowy samego siebie ${\ displaystyle f_ {u}}$ U | razy, co jest oznaczone przez ${\ Displaystyle f_ {u} ^ {\ otimes | U |}.}$ Podobnie, jeśli wierzchołki w V są postrzegane jako jeden duży wierzchołek stopnia | E |, to ograniczeniem tego wierzchołka jest ${\ Displaystyle f_ {v} ^ {\ otimes | V|}.}$ Niech ograniczenie będzie reprezentowane przez jego ważoną $prawdy$ jako wektor wierszowy, a ograniczenie ${v}}$${\ displaystyle$ będzie reprezentowany przez swoją ważoną tabelę prawdy jako wektor kolumnowy. Wtedy Holant tego wykresu ograniczeń to po prostu ${\ Displaystyle f_ {u} ^ {\ otimes | U |} f_ {v} ^ {\ otimes | V|}.}$

Teraz dla dowolnej zespolonej odwracalnej macierzy 2 na 2 T (której kolumny są wspomnianymi powyżej liniowymi wektorami bazowymi) istnieje redukcja holograficzna między ${\ displaystyle {\ text {Holant }}(G, f_{u},f_{v})}$ i ${\ Displaystyle {\ text {Holant}} (G, f_ {u} T ^ {\ otimes (\ deg u)}, (T ^ {-1}) ^ {\ otimes (\ deg v)} f_ {v }).}$ Aby to zobaczyć, wstaw macierz identyczności ${\ Displaystyle T ^ {\ otimes | E |} (T ^ {-1}) ^ {\ otimes | E |}}$ pomiędzy ${\ Displaystyle f_ {u} ^ {\ otimes | U |} f_ {v} ^ {\ otimes | V |}}$ uzyskać

${\ Displaystyle f_ {u} ^ {\ otimes | U |} f_ {v} ^ {\ otimes | V |}}$

${\ Displaystyle = f_ {u} ^ {\ otimes | U |} T ^ {\ otimes | E |} (T ^ {-1}) ^ {\ otimes | E |} f_ {v} ^ {\ otimes | V|}}$

${\ Displaystyle = \ lewo (f_ {u} T ^ {\ otimes (\ stopień u)} \ prawej) ^ {\ otimes | U |} \ lewo (f_ {v} (T ^ {-1}) ^ { \otimes (\deg v)}\right)^{\otimes |V|}.}$

Zatem ${\ Displaystyle {\ tekst {Holant}} (G, f_ {u}, f_ {v})}$ i ${\ Displaystyle {\ text {Holant}} (G, f_ {u} T ^ {\ otimes (\ deg u)}, (T ^ {-1}) ^ {\ otimes (\ deg v)} f_ {v })}$ mają dokładnie taką samą wartość Holanta dla każdego wykresu ograniczeń. Zasadniczo definiują ten sam problem z liczeniem.

Konkretne przykłady

Pokrycia wierzchołków i zbiory niezależne

Niech G będzie grafem. Istnieje zgodność 1 do 1 między pokryciami wierzchołków G a niezależnymi zbiorami G . Dla dowolnego zbioru S wierzchołków G , S jest pokryciem wierzchołków w G wtedy i tylko wtedy, gdy dopełnienie S jest niezależnym zbiorem w G . Zatem liczba pokrycia wierzchołków w G jest dokładnie taka sama, jak liczba niezależnych zbiorów w G .

Równoważność tych dwóch problemów z liczeniem można również udowodnić za pomocą redukcji holograficznej. Dla uproszczenia niech G będzie grafem 3-regularnym . Rozciągnięcie 2 G daje graf dwudzielny H = ( U , V , E ), gdzie U odpowiada krawędziom w G , a V odpowiada wierzchołkom w G . Problem Holanta, który w naturalny sposób odpowiada zliczaniu liczby pokrycia wierzchołków w G , to ${\ Displaystyle {\ text {Holant}} (H, {\ tekst {OR}} _ {2}, {\ text {RÓWNOŚĆ}} _ {3}).} Tabela prawdy$ OR ₂ jako wektor wierszowy to (0,1,1,1). Tabela prawdy RÓWNEGO ₃ jako wektora kolumnowego to ${\ Displaystyle (1,0,0,0,0,0,0,1) ^ {T} = {\ początek {bmatrix} 1 \\0 \ koniec {bmatrix}} ^ {\ czasami 3} + {\ początek{bmacierz}0\\1\koniec{bmacierz}}^{\otimes 3}}$ . Następnie pod holograficzną transformacją przez ${\ Displaystyle {\ rozpocząć {bmatrix} 0 i 1 \\ 1 & 0 \ koniec {bmatrix}},}$

${\ Displaystyle {\ tekst {OR}} _ {2} ^ {\ otimes | U |} {\ tekst {RÓWNE}} _ {3} ^ {\ otimes | V |}}$

${\ Displaystyle = (0,1,1,1) ^ {\ otimes | U |} \ lewo ({\ rozpocząć {bmatrix} 1 \\ 0 \ koniec {bmatrix}} ^ {\ otimes 3} + {\ rozpocząć {bmacierz}0\\1\koniec{bmacierzy}}^{\oraz 3}\right)^{\oraz |V|}}$

${\ Displaystyle = (0,1,1,1) ^ {\ otimes | U |} {\ rozpocząć {bmatrix} 0 i 1 \\ 1 i 0 \ koniec {bmatrix}} ^ {\ otimes | E |} {\ rozpocząć {bmatrix }0&1\\1&0\end{bmatrix}}^{\otimes |E|}\left({\begin{bmatrix}1\\0\end{bmatrix}}^{\otimes 3}+{\begin{bmatrix }0\\1\end{bmatrix}}^{\otimes 3}\right)^{\otimes |V|}}$

${\ Displaystyle = \ lewo ((0,1,1,1) {\ początek {bmatrix} 0 i 1 \\ 1 & 0 \ koniec {bmatrix}} ^ {\ otimes 2} \ prawej) ^ {\ otimes | U |} \ left(\left({\begin{bmatrix}0&1\\1&0\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}\right)^{\otimes 3}+\left( {\begin{bmatrix}0&1\\1&0\end{bmatrix}}{\begin{bmatrix}0\\1\end{bmatrix}}\right)^{\otimes 3}\right)^{\otimes |V |}}$

${\ Displaystyle = (1,1,1,0) ^ {\ otimes | U |} \ lewo ({\ rozpocząć {bmatrix} 0 \\ 1 \ koniec {bmatrix}} ^ {\ otimes 3} + {\ rozpocząć {bmacierz}1\\0\koniec{bmacierz}}^{\otimes 3}\right)^{\otimes |V|}}$

${\ Displaystyle = {\ tekst {NAND}} _ {2} ^ {\ otimes | U |} {\ tekst {RÓWNE}} _ {3} ^ {\ otimes | V |},$

czyli ${\ Displaystyle {\ tekst {Holant}} (H, {\ tekst {NAND}} _ {2}, {\ tekst {RÓWNE}} _ {3}) ,}$ problem Holanta, który w naturalny sposób odpowiada liczeniu niezależnych zbiorów w G .

Historia

Podobnie jak w przypadku każdego rodzaju redukcji, redukcja holograficzna sama w sobie nie daje algorytmu czasu wielomianowego. Aby otrzymać algorytm czasu wielomianowego, redukowany problem musi również mieć algorytm czasu wielomianowego. Oryginalne zastosowanie algorytmów holograficznych Valianta wykorzystywało holograficzną redukcję do problemu, w którym każde ograniczenie jest możliwe do zrealizowania za pomocą bramek dopasowujących, co właśnie udowodnił, że można je rozwiązać poprzez dalszą redukcję do zliczenia liczby doskonałych dopasowań na grafie planarnym . Ten ostatni problem można rozwiązać za pomocą algorytmu FKT , który pochodzi z lat 60. XX wieku.

Wkrótce potem Valiant znalazł algorytmy holograficzne z redukcjami do bramek dopasowujących dla # ₇ Pl -Rtw- Mon -3 CNF i # ₇ Pl-3/2 Bip - VC . Problemy te mogą wydawać się nieco wymyślone, zwłaszcza w odniesieniu do modułu . Oba problemy były już znane jako #P-twarde, gdy zignorowano moduł, a Valiant dostarczył dowody #P-twardości modulo 2, które również wykorzystywały redukcje holograficzne. Valiant znalazł te dwa problemy, przeszukując komputer, który szukał problemów z holograficznymi redukcjami do bramek. Nazwał ich algorytmy algorytmami przypadkowymi , mówiąc: „stosując termin przypadkowy do algorytmu, zamierzamy wskazać, że algorytm powstaje w wyniku spełnienia pozornie uciążliwego zestawu ograniczeń”. „Uciążliwy” zestaw ograniczeń, o których mowa, to równania wielomianowe, które, jeśli są spełnione, implikują istnienie redukcji holograficznej w celu dopasowania możliwych do zrealizowania ograniczeń.

Po kilku latach rozwijania (znanej jako) teorii sygnatur meczowych, Jin-Yi Cai i Pinyan Lu byli w stanie wyjaśnić istnienie dwóch przypadkowych algorytmów Valianta. Te dwa problemy są tylko szczególnymi przypadkami dwóch znacznie większych rodzin problemów: # _{2 ^k -1} Pl-Rtw-Mon-kCNF i # _{2 ^k -1} Pl-k/2Bip-VC dla dowolnej dodatniej liczby całkowitej k . Moduł 7 to tylko trzecia liczba Mersenne'a , a Cai i Lu wykazali, że tego typu problemy z parametrem k można rozwiązać w czasie wielomianowym dokładnie wtedy, gdy moduł jest k -tą liczbą Mersenne'a, stosując holograficzne redukcje do bramek dopasowujących i chińskie twierdzenie o resztach .

Mniej więcej w tym samym czasie Jin-Yi Cai, Pinyan Lu i Mingji Xia opracowali pierwszy algorytm holograficzny, który nie sprowadzał się do problemu, który można rozwiązać za pomocą bramek dopasowujących. Zamiast tego sprowadzili się do problemu, który można rozwiązać za pomocą bramek Fibonacciego, które są symetrycznymi ograniczeniami, których tablice prawdy spełniają relację powtarzalności podobną do tej, która definiuje liczby Fibonacciego . Wykorzystali również redukcje holograficzne, aby udowodnić, że niektóre problemy z liczeniem są #P-trudne. Od tego czasu redukcje holograficzne były szeroko stosowane jako składniki zarówno algorytmów czasu wielomianowego, jak i dowodów twardości #P.