Eliminacja gaussowska pod względem działania grupowego

Eliminacja Gaussa sprawia, że ​​wyznacznik macierzy obliczany jest w czasie wielomianowym. Zmniejszenie złożoności obliczania wyznacznika, które w przeciwnym razie jest sumą terminów wykładniczych, wynika z obecności alternatywnych znaków ujemnych (których brak sprawia, że ​​obliczenia są trwałe, tj. Trudniejszy niż problemy ). Prowadzi to do pewnego rodzaju symetrii w wyznaczniku, np. Wymiana pary wierszy lub kolumn po prostu odwraca znaki. Czytałem gdzieś, prawdopodobnie w związku z algorytmami holograficznymi wprowadzonymi przez Valianta, że ​​eliminację Gaussa można wyjaśnić w kategoriach działania grupowego, a to z kolei prowadzi do ogólnych technik redukcji złożoności.N P -$\#P\mbox{-}hard$$NP\mbox{-}C$

Ponadto uważam, że prawie każde źródło ograniczenia złożoności dowolnego problemu obliczeniowego stanowi pewną symetrię. Czy to prawda? Czy możemy rygorystycznie sformalizować to w kategoriach teorii grup?

Edytować

Znalazłem referencję . (str. 2, ostatni wiersz drugiego akapitu). Nie zrozumiałem poprawnie artykułu. Jeśli moje pytanie dotyczy niewłaściwego zrozumienia artykułu, proszę mnie poprawić.

W przypadku wyznacznika eliminację Gaussa można rzeczywiście uznać za równoważną z ideą, że wyznacznik ma dużą grupę symetrii (określonej postaci) i charakteryzuje się tą grupą symetrii (co oznacza dowolny inny jednorodny stopień wielomianu w zmienne o tych symetriach muszą być skalarną wielokrotnością wyznacznika). (A jeśli chodzi o punkt @Tsuyoshi Ito, że symetrie permanentu wydają się nie pomagać w jego wydajnym obliczeniu: chociaż permanent jest również charakteryzowany przez jego symetrie, jego grupa symetrii jest znacznie mniejsza niż wyznacznika.)$n$$n^2$

Możesz znaleźć opis tego - gdzie symetrie wyznacznika służą do eliminacji Gaussa, po drodze udowadniając, że wyznacznik charakteryzuje się symetriami - w Propozycji 3.4.3 mojej tezy (bezwstydna wtyczka - ale też nigdy wcześniej nie widziałem tego tak sformułowanego i napisanego szczegółowo, o co poprosił PO, choć jestem pewien, że zostało zrobione; byłbym szczęśliwy, gdyby ktoś miał inne odniesienia).

Jeśli chodzi o ideę, że symetria zawsze prowadzi do zmniejszenia złożoności (lub nie), oprócz rzeczy już w komentarzach, zobacz to pytanie i jego odpowiedzi.

Ciekawe jest to, że w pierwszych pracach Valianta na temat tak zwanej wersji teorii algebraicznej złożoności Valianta starał się stwierdzić, że jednym z powodów, dla których wyznacznik jest ważny obliczeniowo, jest to, że z grubsza wszystkie (wówczas) znane skuteczne algorytmy mogą być zredukowane do algebry liniowej, a tym samym do obliczenia wyznacznika, np. algorytmu FKT do zliczania dopasowań w grafach płaskich. Jest to oczywiście przesada, ale nadal znajduje potwierdzenie w badaniach algorytmów holograficznych, które często sprowadzają się do obliczenia Pfaffiana (bliskiego krewnego wyznacznika). Z pewnością Valiant wiedział, że to przesada, ale oto dokładny cytat, aby upewnić się, że nie wprowadzam w błąd ( L. Valiant. Klasy kompletności w algebrze. ACM STOC 1979 ):

Nasze główne wnioski można podsumować mniej więcej w następujący sposób:

(a) Algebra liniowa oferuje zasadniczo jedyną szybką technikę obliczania wielowymiarowych wielomianów umiarkowanego stopnia

(b) ...

Są przypadki, w których symetrie problemu (wydają się) charakteryzują jego złożoność. Jednym z bardzo interesujących przykładów są problemy związane z satysfakcją z ograniczeń (CSP).

Definicja CSP

CSP jest podawany przez domenę i język ograniczeń ( -ary działa od do ). Instancja spełnienia ograniczenia jest podana przez zestaw zmiennych i ograniczenia z . Rozwiązaniem instancji jest przypisanie dzięki czemu wszystkie ograniczenia są spełnione.$U$$\Gamma$$k$$U^k$$\{0, 1\}$$V$$\Gamma$$\phi:V \rightarrow U$

Na przykład w tym języku 3-SAT jest podane przez który jest zbiorem wszystkich rozłączeń 3 literałów, to po prostu . W innym przykładzie układy równań liniowych mod 2 są podane przez czyli wszystkie równania liniowe mod 2 z zmiennych, a to znowu .$\Gamma$$U$$\{0, 1\}$$\Gamma$$k$$U$$\{0, 1\}$

Polimorfizmy

Istnieje poczucie, że twardość CSP charakteryzuje się symetriami. Omawiane symetrie nazywane są polimorfizmami. Polimorfizm jest sposobem lokalnego połączenia kilku rozwiązań z CSP w celu uzyskania nowego rozwiązania. Lokalnie tutaj oznacza, że ​​istnieje funkcja, która jest stosowana do każdej zmiennej osobno. Dokładniej, jeśli masz kilka rozwiązań (spełniających zadania) , polimorfizm jest funkcją którą można zastosować do każdej zmiennej w celu uzyskania nowego rozwiązania : . Aby był polimorfizmem, powinien odwzorować wszystkie krotki f : U t → U ϕ ϕ ( v ) = f ( ϕ 1 ( v ) , … , ϕ t ( v ) ) f $\phi_1, \ldots, \phi_t$$f:U^t \rightarrow U$$\phi$$\phi(v) = f(\phi_1(v), \ldots, \phi_t(v))$$f$$t$ spełnianie przypisań do dowolnej instancji spełniające przypisanie do tej samej instancji.

Polimorfizmem dla układów równań liniowych jest na przykład . Zauważ, że . , który spełnia tę właściwość jest znany jako operacja Maltsev. CSP z polimorfizmem Maltseva można rozwiązać przez eliminację Gaussa.f ( x , x , y ) = f ( y , x , x ) = y $f(x, y, z) = x + y + z \pmod 2$$f(x, x, y) = f(y, x, x) = y$$f$

Z drugiej strony rozłączenia 3 literałów mają tylko dyktatory jako polimorfizmy, tj. Funkcje typu .$f(x, y) = x$

Polimorfizmy i złożoność (hipoteza dychotomii)

Polimorfizmy w rzeczywistości mają implikacje obliczeniowe: jeśli CSP wszystkie polimorfizmy z , wówczas jest czasem wielomianowym redukowalnym do . Jest to sposób na formalne stwierdzenie, że CSP który jest „mniej symetryczny” niż inny CSP jest w rzeczywistości trudniejszy.Γ 2 Γ 1 Γ 2 Γ 2 Γ $\Gamma_1$$\Gamma_2$$\Gamma_1$$\Gamma_2$$\Gamma_2$$\Gamma_1$

Głównym otwartym problemem w teorii złożoności jest scharakteryzowanie twardości CSP. Hipoteza Feder i Vardi dotycząca dychotomii stwierdza, że ​​każdy CSP jest w P lub NP-kompletny. Hipotezę można sprowadzić do stwierdzenia o polimorfizmach: CSP jest trudny do NP, i tylko wtedy, gdy jedynymi dopuszczonymi przez niego polimorfizmami są „dyktatorzy” (w przeciwnym razie jest to P). Tj. CSP jest trudny tylko wtedy, gdy nie ma lokalnego sposobu na tworzenie autentycznych nowych rozwiązań ze starych rozwiązań. Część if (twardość) jest znana, ale tylko jeśli część (projektowanie algorytmu czasu policyjnego) jest otwarta.

Jednak ważnym przypadkiem, w którym mamy dychotomię, są logiczne CSP (gdzie ). Zgodnie z twierdzeniem Schaefera , boolowski CSP znajduje się w P, jeśli dopuszcza jeden z 6 polimorfizmów, w przeciwnym razie jest NP-kompletny. Sześć polimorfizmów jest w zasadzie tym, czego potrzebujesz, aby rozwiązać problem albo przez eliminację gaussa, albo przez rozmnażanie (jak na przykład w przypadku Horn-Sat), lub w celu rozwiązania go przez trywialne zadanie.$U = \{0, 1\}$

Aby dowiedzieć się więcej na temat polimorfizmów, algebry uniwersalnej i hipotezy dychotomii, zapoznaj się z ankietą Bułatowa .

Polimorfizmy i przybliżalność

Polecam także wykład MSR Prasad Raghavendra, w którym umieszcza swój wynikco daje optymalne przybliżenie dowolnego CSP, zakładając unikalną hipotezę gier w podobnej strukturze. Na wysokim poziomie, jeśli wszystkie polimorfizmy (które muszą być uogólnione, aby poradzić sobie z problemami z aproksymacją) CSP są zbliżone do dyktatorów, można użyć CSP do zaprojektowania sposobu sprawdzenia, czy funkcja jest dyktatorem, i okazuje się, że być wszystkim, czego potrzebujesz, aby uzyskać stopień zmniejszenia przybliżenia w przypadku unikalnych gier. Daje to kierunek twardości jego wyniku; kierunek algorytmu jest taki, że gdy CSP ma polimorfizm daleki od dyktatora, można zastosować zasadę niezmienniczości (uogólnienie twierdzeń o granicy centralnej), aby argumentować, że algorytm zaokrąglania SDP daje dobre przybliżenie. Naprawdę szkicowa intuicja dla części algorytmicznej: polimorfizm daleki od dyktatora nie robi nie przejmuj się, jeśli podano go jako argumenty (rozkład względem) przypisań zmiennych lub losowe zmienne gaussowskie, które lokalnie przybliżają rozkład przypisań zmiennych. Jest to ten sam sposób, w jaki funkcja sumy „nie przejmuje się”, jeśli centralne twierdzenie graniczne podaje dyskretne zmienne losowe o małej wariancji lub gavian rv o tej samej wariancji. Potrzebne nam zmienne losowe gaussowskie można obliczyć z relaksacji SDP problemu CSP. Tak więc znajdujemy polimorfizm daleki od dyktatora, karmimy go próbkami gaussowskimi i odzyskujemy dobre rozwiązanie. jeśli podano dyskretne zmienne losowe o małej wariancji lub gavsv rv o tej samej wariancji, według centralnego twierdzenia granicznego. Potrzebne nam zmienne losowe gaussowskie można obliczyć z relaksacji SDP problemu CSP. Tak więc znajdujemy polimorfizm daleki od dyktatora, karmimy go próbkami gaussowskimi i odzyskujemy dobre rozwiązanie. jeśli podano dyskretne zmienne losowe o małej wariancji lub gavsv rv o tej samej wariancji, według centralnego twierdzenia granicznego. Potrzebne nam zmienne losowe gaussowskie można obliczyć z relaksacji SDP problemu CSP. Tak więc znajdujemy polimorfizm daleki od dyktatora, karmimy go próbkami gaussowskimi i odzyskujemy dobre rozwiązanie.