Pourquoi le CYCLE HAMILTONIEN est-il si différent de PERMANENT?

Un polynôme est une projection monotone d'un polynôme si = poly , et il y a une affectation $f(x_1,\ldots,x_n)$ $g(y_1,\ldots,y_m)$ $m$ $(n)$ tel que . Autrement dit, il est possible de remplacer chaque variable de par une variable ou une constante ou sorte que le polynôme résultant coïncide avec . $\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$

Je m'intéresse (aux raisons) à la différence entre le polynôme permanent PER et le polynôme de cycle hamiltonien HAM: où la première sommation est sur toutes les permutations

{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)}$

, et la seconde ne concerne que touteslespermutationscycliques

h : [n] \to [n]

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

h : [n] \to [n]

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

Question: Pourquoi HAM est pas une projection monotone PER? Ou c'est toujours le cas?

Je ne demande pas preuves , juste pour des raisons intuitives.

Motivation: le plus grand circuit monotone connu inférieur pour PER (prouvé par Razborov) reste "seulement" . D'autre part, les résultats de Valiant impliquent que où à la sommation est faite sur toutes les sous - ensembles de taille $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]$

. Je n'ai pas pu obtenir moi-même une réduction "simple et directe" de ces résultats généraux, maisAlon et Boppanaaffirment (dans la section 5) que déjà

| S | = \sqrt{n}

$|S|=\sqrt{n}$

m = 25 n^{2}

$m=25n^2$ est suffisant pour cette réduction.

Mais attendez: il est bien connu que CLIQUE nécessite des circuits monotones de taille $2^{n^{\Omega(1)}}$ (d'abord prouvé par Alon et Boppana en utilisant la méthode de Razborov).

Donc, si HAM était une projection monotone de PER, nous aurions $2^{n^{\Omega(1)}}$ borne inférieure pour PER.

En fait, pourquoi HAM n'est même pas une projection non monotone de PER? Au cours de la semianneau booléen, le premier est NP -complete, alors que ce dernier est en P . Mais pourquoi? Où est un endroit où être cyclique pour une permutation la rend si spéciale?

PS Une différence évidente pourrait être: HAM couvre [n] par un seul (long) cycle, alors que PER peut utiliser des cycles disjoints pour cela. Ainsi, pour projeter PER vers HAM, la direction difficile semble être: s'assurer que l' absence d'un cycle hamiltonien implique l'absence de toute couverture à cycles disjoints dans le nouveau graphe. Est-ce la raison pour laquelle HAM n'est pas une projection de PER?

PPS En fait, Valiant a démontré un résultat plus impressionnant: chaque polynôme avec , dont les coefficients sont calculables en temps p , est une projection (pas nécessairement monotone si l'algo n'est pas monotone) de HAM pour = poly $f(x)=\sum_{u\subseteq [n]}c_u\prod_{i\in u}x_i$ $c_u\in\{0,1\}$ $c_u$ $_m$ $m$ $(n)$ . PER possède également cette propriété, mais uniquement sur des champs de caractéristique . Donc, dans ce sens, HAM et PER sont en effet "similaires", à moins que nous ne soyons pas dans GF (2) où, comme Bruno s'en souvient, PER se tourne vers DETERMINANT, et c'est facile. $\neq 2$

cc.complexity-theory circuit-complexity lower-bounds arithmetic-circuits Stasys
la source

J'ai une question un peu hors du sujet. Puis-je demander pourquoi PERMANENT est en P sur le semiring booléen? Je ne connais pas un tel algorithme.

caozhu

@caozhu: C'est tout simplement parce que PERMANENT est identique à DETERMINANT sur le semiring booléen. L'algorithme est alors n'importe quel algorithme DETERMINANT.

Bruno

@Bruno: pas tout à fait. Vous avez raison si nous sommes dans le domaine GF (2); alors nous pouvons utiliser, disons, Gauss. Pourtant, booléen

circuit pour PER de tailleenviron

peuvent être construitsaidealgorithme Hopcroft-Karppourcorrespondance maximale, ou tout simplement algorithme de défaut maximum Floyd-Fulkerson.

{\lor, \land, \neg}

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

n^{5 / 2}

$n^{5/2}$

Stasys

Ce qui suit est une preuve sur tout anneau de zéro caractéristique que le polynôme de cycle hamiltonien n'est pas une projection monotone de taille polynomiale du permanent. L'idée de base est que les projections monotones de polynômes avec des coefficients non négatifs conduisent au polytope de Newton de l'un étant une formulation étendue du polytope de Newton de l'autre, puis en appliquant les limites inférieures récentes sur des formulations étendues.

$f(x_1,\dotsc,x_n)$ $g(y_1,\dotsc,y_m)$ $f$ $g$ $\pi$ $\pi$ $g$ $f$ : il ne peut pas y avoir d'annulation à cause de la non-négativité.

Laisser $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
la source

un très bel argument. C'est exactement ce que je cherchais! En effet, les formulations LP étendues simulent les projections de Valiant (au moins monotones).

Stasys

Pourquoi le CYCLE HAMILTONIEN est-il si différent de PERMANENT?

Réponses: