Dlaczego CYKL HAMILTONICZNY tak różni się od STAŁEGO?

23

Wielomian f ( x 1 , , x n )f(x1,,xn) jest rzutem monotonicznym wielomianu g ( y 1 , , y m ),g(y1,,ym) jeśli = poli , i istnieje przypisanie takie, że . Oznacza to, że możliwe jest zastąpienie każdej zmiennej o o zmiennej lub stałą lubm ( n ) π : { y 1 , , y m } { x 1 , , x n , 0 , 1 } f ( x 1 , , x n ) = g ( π ( y 1 ) , , π ( y m ) ) y j g x im(n)π:{y1,,ym}{x1,,xn,0,1}f(x1,,xn)=g(π(y1),,π(ym))yjgxi0 101 tak że wynikowy wielomian pokrywa się z . faf

Interesuje mnie (przyczyny) różnica między stałym wielomianem PER a wielomianem cyklu Hamiltona HAM: gdzie pierwsze sumowanie dotyczy wszystkich permutacji , a drugie dotyczy tylko wszystkich permutacji cyklicznych . PER n (x)=h n i = 1 x i , h ( i ) i HAM n (x)=h n i = 1 x i , h ( i )        

PERn(x)=hi=1nxi,h(i)    and    HAMn(x)=hi=1nxi,h(i)
h : [ n ] [ n ]h:[n][n]h : [ n ] [ n ]h:[n][n]
Pytanie: Dlaczego HAM nie jest projekcją monotoniczną PER? Czy nadal tak jest?
Nie proszę o dowody , tylko z intuicyjnych powodów.

Motywacja: największa znana dolna granica obwodu monotonicznego dla PER (udowodniona przez Razborova) pozostaje „tylko” . Z drugiej strony wyniki Valiant sugerują, że gdzie z sumą dotyczy wszystkich podzbiorów o rozmiarze . Sam nie mogłem uzyskać „prostej, bezpośredniej” redukcji z tych ogólnych wyników, ale Alon i Boppana twierdzą (w rozdz. 5), że już jest wystarczające do tej redukcji. n Ω ( log n )nΩ(logn)CLIQUEn is a monotone projection of HAMm

CLIQUEn is a monotone projection of HAMm
CLIQUEn(x)=Si<jSxi,j
CLIQUEn(x)=Si<jSxi,j
S[n]S[n]|S|=n|S|=nm=25n2m=25n2

Ale czekaj: dobrze wiadomo, że CLIQUE wymaga obwodów monotonicznych o rozmiarze (po raz pierwszy udowodnione przez Alona i Boppana metodą Razborova). 2nΩ(1)2nΩ(1)

Gdyby HAM był monotoniczną projekcją PER, mielibyśmy dolną granicę również dla PER. 2nΩ(1)2nΩ(1)

Właściwie dlaczego HAM nie jest nawet niemonotoniczną projekcją PER? Przez logicznej semiring, były to NP -Complete, podczas gdy ten ostatni znajduje się w P . Ale dlaczego? Gdzie jest miejsce, w którym cykliczność permutacji czyni ją tak wyjątkową?

PS Jedną oczywistą różnicą może być: HAM obejmuje [n] tylko jednym (długim) cyklem, podczas gdy PER może używać do tego celu rozłącznych cykli. Tak więc, aby rzutować PER do HAM, trudnym kierunkiem wydaje się być: zapewnienie, że brak cyklu hamiltonowskiego oznacza brak pokrycia z rozłącznymi cyklami na nowym wykresie. Czy to jest powód, dla którego HAM nie jest projekcją PER?

PPS Właściwie Valiant okazał się bardziej imponującym wynikiem: każdy wielomian z c u{ 0 , 1 } , którego współczynniki c u są obliczalne w czasie p, to rzut (niekoniecznie monotoniczny, jeśli algo nie jest monotoniczny) HAM m dla m = poli ( n ) . PER ma również tę właściwość, ale tylko ponad polami charakterystycznymi . W tym sensie HAM i PER f(x)=u[n]cuiuxif(x)=u[n]cuiuxicu{0,1}cumm(n)22 w rzeczy samej „podobny”, chyba że nie znajdujemy się w GF (2), w którym, jak pamiętał Bruno, PER zwraca się do DETERMINANTA i jest łatwe.

Stasys
źródło
1
Mam pytanie nieco poza tematem. Czy mogę zapytać, dlaczego PERMANENT jest w P w porównaniu do semestru boolowskiego? Nie znam takiego algorytmu.
caozhu
@caozhu: Dzieje się tak po prostu dlatego, że PERMANENT jest taki sam jak DETERMINANT podczas semestru boolowskiego. Algorytm jest wówczas dowolnym algorytmem DETERMINANT.
Bruno,
3
@Bruno: niezupełnie. Masz rację, jeśli jesteśmy w polu GF (2); wtedy możemy użyć, powiedzmy, Gaussa. Mimo logiczna { , , Ź } obwód PER wielkości o n 5 / 2 może być wykonana przy użyciu algorytmu Hopcroft-Karp maksymalne dopasowanie albo tylko algorytmu maksymalnego wad Floyd- Fulkersona. {,,¬}n5/2
Stasys,

Odpowiedzi:

9

Poniżej znajduje się dowód na każdy pierścień o charakterystycznym zeru, że wielomian cyklu hamiltonowskiego nie jest wielomianowym rzutem monotonicznym stałej. Podstawową ideą jest to, że monotoniczne projekcje wielomianów o nieujemnych współczynnikach prowadzą do tego, że polytop Newtona z jednej jest rozszerzoną formułą polytopu Newtona z drugiej, a następnie nakłada ostatnie dolne granice na rozszerzone formulacje.

Niech f ( x 1 , ... , x n ) i g ( Y 1 , ... , T m ) być wielomiany współczynnikach nieujemne (tak jak w tym przypadku). Załóżmy, że f jest rzutem monotonicznym g pod przyporządkowaniem π (zgodnie z notacją pytania). Pod π każdy monomial g jest odwzorowywany albo na 0 (iff jedna z jego zmiennych zostaje zmapowana na 0) lub na monomial f : nie można anulować z powodu braku negatywności.f(x1,,xn)g(y1,,ym)fgππgf

Niech N e w ( f ) oznacza politton Newtona f i podobnie dla N e w ( g ) .New(f)fNew(g)

Twierdzenie : istnieje rozszerzone sformułowanie dla N e w ( f ) w R m , wykorzystujące zmienne n + m , oraz szereg ograniczeń, które są co najwyżej n + m plus liczba ograniczeń definiujących N e w ( g ) .New(f)Rmn+mn+mNew(g)

Oto jak: Niech e 1 , , e m będą współrzędnymi na R m (w których żyje N e w ( g ) ; mianowicie, liczba całkowita w R m ze współrzędnymi ( e 1 , , e m ) odpowiada monomial y e 1 1y e m m ). Dla tych i takich, że π ( y i ) =e1,,emRmNew(g)Rm(e1,,em)ye11yemmi0 , przecinaj N e w ( g ) z { e i = 0 } (ponieważ tylko monomiały, które nie obejmują y i, mogą przyczynić się do projekcji); dodaje to co najwyżej m dodatkowe ograniczenia. Niech P oznacza wynikowy polytop. Następnie π indukuje mapę liniową L π : R mR n , taką, że L π ( P ) = N e w ( f )π(yi)=0New(g){ei=0}yimPπLπ:RmRnLπ(P)=New(f). Ta ostatnia część wynika z braku odwołań. W ten sposób uzyskać preparat o przedłużonym dla N e wagowo ( f ) poprzez n + m zmienne, ograniczenia dla P dotyczące m zmienne, ograniczenia określające L gatunku (z których co najwyżej n , po jednym dla każdego x I ) . Roszczenie QEDNew(f)n+mPmLπnxi

Przyjmijmy teraz, że f jest n-tym wielomianem cyklu Hamiltona, a g jest m-tym stałym, i załóżmy, że f jest rzutem monotonicznym g . Polytop Newtona trwałego (i nawiasem mówiąc, nawiasem mówiąc,) jest polytopem na pokrycie cyklu. Ten polytop można łatwo opisać za pomocą zmiennych „krawędzi” e i j oraz równań m stwierdzających, że każdy wierzchołek ma stopień dokładnie 2.fngmfgeijm

Polytop szynki Newtona. Wielomian cyklu jest wielościanem cyklu Hamiltoniana (niespodzianka, niespodzianka). Ale ten polytop jest polytopem TSP, który wymaga 2 równań 2 n Ω ( 1 ), aby opisać dowolne rozszerzone sformułowanie2nΩ(1) , które, gdy m jest subeksponencjalny, jest sprzeczne z małym rozszerzonym sformułowaniem podanym przez polytop pokrywający cykl i L π jak powyżej.mLπ

(Zauważ, że ten argument nie powiedzie się, jeśli f , g lub π mogą mieć ujemne współczynniki, ponieważ wtedy mogą wystąpić odwołania, więc L π nie musi mapować na N e w ( f ) .)fgπLπNew(f)

To ciekawe, że geometria tych polytopes jest ściśle związane z faktem, że dopasowanie jest w P podczas cyklu Hamiltona jest N P -Complete, ale myślę, że powyższe programy rozumowania jak struktura geometryczna tutaj naprawdę można dodać coś poza tą klasyfikacją złożoności .

Joshua Grochow
źródło
1
a very nice argument. This is exactly what I looked for! Indeed, extended LP formulations simulate Valiant's projections (at least monotone).
Stasys