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

23

Un polynôme est une projection monotone d'un polynôme g ( y 1 , , y m ) si m = poly ( n ) , et il y a une affectation π : { y 1 , , y m } { x 1 , , x n , 0 ,f(x1,,xn)g(y1,,ym)m(n) tel que f ( x 1 , , x n ) = g ( π ( y 1 ) , , π ( y m ) ) . Autrement dit, il est possible de remplacer chaque variable y j de g par une variable x i ou une constante 0 ou 1 de sorte que le polynôme résultant coïncide avec f . π:{y1,,ym}{x1,,xn,0,1}f(x1,,xn)=g(π(y1),,π(ym))yjgxi01f

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 h : [

PERn(x)=hi=1nxi,h(i)    and    HAMn(x)=hi=1nxi,h(i)
, et la seconde ne concerne que touteslespermutationscycliques h : [ n ] [ n ] . h:[n][n]h:[n][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 CLIQUE n  est une projection monotone de HAM mCLIQUE n ( x ) = Σ S Π i < j S x i , j à la sommation est faite sur toutes les sous - ensembles de [ s n ] de taille | S |nΩ(logn)

CLIQUEn is a monotone projection of HAMm
CLIQUEn(x)=Si<jSxi,j
S[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àm=25n2|S|=nm=25n2 est suffisant pour cette réduction.

Mais attendez: il est bien connu que CLIQUE nécessite des circuits monotones de taille 2nΩ(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 2nΩ(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 c u{ 0 , 1 } , dont les coefficients c u sont calculables en temps p , est une projection (pas nécessairement monotone si l'algo n'est pas monotone) de HAM m pour m = poly ( n )f(x)=u[n]cuiuxicu{0,1}cumm(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.2

Stasys
la source
1
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
3
@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 n cinq / deux peuvent être construitsaidealgorithme Hopcroft-Karppourcorrespondance maximale, ou tout simplement algorithme de défaut maximum Floyd-Fulkerson. {,,¬}n5/2
Stasys

Réponses:

9

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(x1,,xn)g(y1,,ym)fgππgf : il ne peut pas y avoir d'annulation à cause de la non-négativité.

Laisser New(f)fNew(g)

New(f)Rmn+mn+mNew(g) .

e1,,emRmNew(g)Rm(e1,,em)y1e1ymemiπ(yi)=0New(g){ei=0}yimPπLπ:RmRnLπ(P)=New(f)New(f)n+mPmLπnxi

fngmfgeijm

2nΩ(1)mLπ

fgπLπNew(f) .)

PNP

Joshua Grochow
la source
1
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