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

Wielomian $f(x_1,\ldots,x_n)$ jest rzutem monotonicznym wielomianu $g(y_1,\ldots,y_m)$ 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 $m$$(n)$$\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$$f(x_1,\ldots,x_n)=g(\pi(y_1),\ldots,\pi(y_m))$$y_j$$g$$x_i$0 $0$$1$ tak że wynikowy wielomian pokrywa się z . $f$

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 .

$$\mbox{PER}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}\ \ \ \ \mbox{and} \ \ \ \ \mbox{HAM}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}$$ $h:[n]\to[n]$$h:[n]\to[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^{\Omega(\log n)}$

$$\mbox{CLIQUE$_n$ is a monotone projection of HAM$_{m}$}$$ $$\mbox{CLIQUE}_n(x)=\sum_{S}\prod_{i < j\in S}x_{i,j}$$ $S\subseteq [n]$$|S|=\sqrt{n}$$m=25n^2$

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

Gdyby HAM był monotoniczną projekcją PER, mielibyśmy dolną granicę również dla PER. $2^{n^{\Omega(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 są$f(x)=\sum_{u\subseteq [n]}c_u\prod_{i\in u}x_i$$c_u\in\{0,1\}$$c_u$$_m$$m$$(n)$$\neq 2$ 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.

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(x_1,\dotsc,x_n)$$g(y_1,\dotsc,y_m)$$f$$g$$\pi$$\pi$$g$$f$

Niech N e w ( f ) oznacza politton Newtona f i podobnie dla N e w ( g ) .$New(f)$$f$$New(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)$$\mathbb{R}^m$$\leq n+m$$n+m$$New(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 1 ⋯ y e m m ). Dla tych i takich, że π ( y i ) $e_1,\dotsc,e_m$$\mathbb{R}^m$$New(g)$$\mathbb{R}^m$$(e_1,\dotsc,e_m)$$y_1^{e_1} \dotsb y_m^{e_m}$$i$0 , 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 m → R n , taką, że L π ( P ) = N e w ( f $\pi(y_i)=0$$New(g)$$\{e_i = 0\}$$y_i$$m$$P$$\pi$$L_{\pi}\colon \mathbb{R}^{m} \to \mathbb{R}^{n}$$L_{\pi}(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 QED$New(f)$$n+m$$P$$m$$L_{\pi}$$n$$x_i$

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.$f$$n$$g$$m$$f$$g$$e_{ij}$$m$

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łowanie$2^{n^{\Omega(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.$m$$L_{\pi}$

(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 ) .)$f$$g$$\pi$$L_{\pi}$$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 .$\mathsf{P}$$\mathsf{NP}$