Eliminacja gaussowska pod względem działania grupowego

13

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 - C#P-hardNP-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ć.

DurgaDatta
źródło
3
Moje osobiste podejście do drugiego akapitu: problemy o dużym zainteresowaniu często mają symetrię, niezależnie od tego, czy mają wydajne algorytmy, czy nie. Ale poza tym nie widzę prawdy w twoim odczuciu, że „prawie każde źródło ograniczenia złożoności dla dowolnego problemu obliczeniowego jest jakąś obecną symetrią”. Na przykład nie widzę, jakiej algorytmu używa algorytm Kruskala. Co więcej, pogląd, że wydajne algorytmy powstają z symetrii problemów, nie wydaje się wyjaśniać, dlaczego symetria wartości stałej najwyraźniej nie pomaga w jej wydajnym obliczeniu.
Tsuyoshi Ito
4
Nie, symetria nie zawsze obniża złożoność. Każde interesujące pytanie dotyczące grup jest nierozstrzygalne. Sortowanie nie jest.
Jeffε
2
najbliższym formalnym stwierdzeniem w tym kierunku, które przychodzi mi na myśl, jest algebraiczna hipoteza dychotomii, która (mówiąc bardzo niejasno) stwierdza, że ​​CSP jest w P wtedy i tylko wtedy, gdy istnieją nietypowe sposoby połączenia dwóch rozwiązań w prawdziwie odmienne trzecie rozwiązanie . jednym z przykładów jest rozwiązanie modu systemu liniowego 2, który można rozwiązać przez eliminację gaussa, i gdzie dwa różne rozwiązania określają afiniczną podprzestrzeń rozwiązań
Sasho Nikolov
2
ah, więc tak naprawdę mówisz o GCT, który zaczyna się od idei, że problem permanentny vs. determinant można zrozumieć w kategoriach (z grubsza) symetrii, pod którymi dwie funkcje są niezmienne.
Sasho Nikolov
2
Istnieje wiele powodów, dla których problem dopuszcza wydajny algorytm. Wypukłość, submodułowość itp. Symetrie powodują wybuch przypadku w niektórych problemach kombinatorycznych i są czasami postrzegane jako źródło nieefektywności.
Vijay D

Odpowiedzi:

12

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.)nn2

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) ...

Joshua Grochow
źródło
7

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ΓkUk{0,1}VΓϕ:VU

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 .ΓU{0,1}ΓkU{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 tU ϕ ϕ ( v ) = f ( ϕ 1 ( v ) , , ϕ t ( v ) ) f tϕ1,,ϕtf:UtUϕϕ(v)=f(ϕ1(v),,ϕt(v))ft 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 ff(x,y,z)=x+y+z(mod2)f(x,x,y)=f(y,x,x)=yf

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 Γ 1Γ1Γ2Γ1Γ2Γ2Γ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.

Sasho Nikolov
źródło
2
Bułatow wygłosił również zaproszone przemówienie na temat swojej ankiety podczas CSR 2011.
Tyson Williams