¿Por qué el CICLO HAMILTONIANO es tan diferente del PERMANENTE?

Un polinomio es una proyección monótona de un polinomio si = poly , y hay una asignación manera que . Es decir, es posible reemplazar cada variable de por una variable o una constante o para que el polinomio resultante coincida con . $f(x_1,\ldots,x_n)$ $g(y_1,\ldots,y_m)$ $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$ $1$ $f$

Estoy interesado en (las razones) la diferencia entre el polinomio permanente PER y el polinomio HAM hamiltoniano: donde la primera suma es sobre todas las permutaciones , y la segunda es solo sobre todas las permutaciones cíclicas .

{PER}_{n} (x) = \sum_{h} \prod_{i = 1}^{n} x_{i, h (i)} and {HAM}_{n} (x) = \sum_{h} \prod_{i = 1}^{n} x_{i, h (i)}

$\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]$

h : [n] \to [n]

$h:[n]\to[n]$

Pregunta: ¿Por qué HAM no es una proyección monótona PER? O todavía lo es?

No estoy pidiendo pruebas , solo por razones intuitivas.

Motivación: el mayor circuito monótono conocido con límite inferior para PER (probado por Razborov) sigue siendo "solo" . Por otro lado, los resultados de Valiant implican que donde con la suma es sobre todos los subconjuntos de tamaño . Yo mismo no podría obtener una reducción "simple y directa" de estos resultados generales, pero Alon y Boppana afirman (en la Sección 5) que ya es suficiente para esta reducción. $n^{\Omega(\log n)}$

CLIQUE_{n} is a monotone projection of HAM_{m}

$\mbox{CLIQUE$_n$ is a monotone projection of HAM$_{m}$}$

{CLIQUE}_{n} (x) = \sum_{S} \prod_{i < j \in S} x_{i, j}

$\mbox{CLIQUE}_n(x)=\sum_{S}\prod_{i < j\in S}x_{i,j}$

S \subseteq [n]

$S\subseteq [n]$

| S | = \sqrt{n}

$|S|=\sqrt{n}$

m = 25 n^{2}

$m=25n^2$

Pero espere: es bien sabido que CLIQUE requiere circuitos monótonos de tamaño (probado por primera vez por Alon y Boppana usando el método de Razborov). $2^{n^{\Omega(1)}}$

Entonces, si HAM fuera una proyección monótona de PER, tendríamos límite inferior también para PER. $2^{n^{\Omega(1)}}$

En realidad, ¿por qué HAM ni siquiera es una proyección no monótona de PER? Durante el semiring boolean, el primero es NP -Complete, mientras que el último está en P . ¿Pero por qué? ¿Dónde está un lugar donde ser cíclico para una permutación lo hace tan especial?

PD Una diferencia obvia podría ser: HAM cubre [n] solo por un ciclo (largo), mientras que PER puede usar ciclos disjuntos para esto. Por lo tanto, para proyectar PER a HAM, la dirección difícil parece ser: asegurarse de que la ausencia de un ciclo hamiltoniano implique la ausencia de cualquier cobertura con ciclos disjuntos en el nuevo gráfico. ¿Es esta la razón por la que HAM no es una proyección de PER?

PPS En realidad, Valiant demostró un resultado más impresionante: cada polinomio con , cuyo Los coeficientes son computables en tiempo p, es una proyección (no necesariamente monótona si el algo no es monótona) de HAM para = poli . PER también tiene esta propiedad, pero solo sobre campos de característica . Entonces, en este sentido, HAM y PER son de hecho "similares", a menos que no estemos en GF (2) donde, como Bruno recordó, PER recurre a DETERMINANTE, y es fácil. $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$

cc.complexity-theory circuit-complexity lower-bounds arithmetic-circuits Stasys
fuente

Tengo una pregunta un poco fuera del tema. ¿Puedo preguntar por qué PERMANENTE está en P sobre el semiseño booleano? No estoy al tanto de tal algoritmo.

caozhu

@caozhu: Esto es simplemente porque PERMANENTE es lo mismo que DETERMINANTE sobre el semiseño booleano. El algoritmo es entonces cualquier algoritmo DETERMINANTE.

Bruno

@ Bruno: no del todo. Tiene razón si estamos en el campo GF (2); entonces podemos usar, digamos, Gauss. Aún así, boolean

circuito para PER de tamaño sobre

puede construirse utilizando algoritmo Hopcroft-Karp para la máxima coincidencia, o simplemente Floyd-Fulkerson algoritmo máximo de defecto.

{\lor, \land, \neg}

$\{\lor,\land,\neg\}$

n^{5 / 2}

$n^{5/2}$

Stasys

La siguiente es una prueba sobre cualquier anillo de característica cero de que el polinomio del ciclo hamiltoniano no es una proyección monótona de tamaño polinómico del permanente. La idea básica es que las proyecciones monótonas de polinomios con coeficientes no negativos conducen a que el politopo de Newton sea una formulación extendida del politopo de Newton de la otra, y luego aplique los límites inferiores recientes en formulaciones extendidas.

$f(x_1,\dotsc,x_n)$ $g(y_1,\dotsc,y_m)$ $f$ $g$ $\pi$ $\pi$ $g$ $f$

$New(f)$ $f$ $New(g)$

$New(f)$ $\mathbb{R}^m$ $\leq n+m$ $n+m$ $New(g)$

$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$ $\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)$ $New(f)$ $n+m$ $P$ $m$ $L_{\pi}$ $n$ $x_i$

$f$ $n$ $g$ $m$ $f$ $g$ $e_{ij}$ $m$

$2^{n^{\Omega(1)}}$ $m$ $L_{\pi}$

$f$ $g$ $\pi$ $L_{\pi}$ $New(f)$

$\mathsf{P}$ $\mathsf{NP}$

Joshua Grochow
fuente

Un muy buen argumento. ¡Esto es exactamente lo que buscaba! De hecho, las formulaciones de LP extendidas simulan las proyecciones de Valiant (al menos monótono).

Stasys

¿Por qué el CICLO HAMILTONIANO es tan diferente del PERMANENTE?

Respuestas: