Por que o CICLO HAMILTONIANO é tão diferente de PERMANENTE?

23

Um polinômio é uma projeção monótona de um polinômio g ( y 1 , , y m ) se m = poli ( n ) , e existe uma atribuição π : { y 1 , , y m } { x 1 , , x n , 0 , 1f(x1,,xn)g(y1,,ym)m(n) tal que f ( x 1 , , x n ) = g ( π ( y 1 ) , , π ( y m ) ) . Ou seja, é possível substituir cada variável y j de g por uma variável x i ou uma constante 0 ou 1, para que o polinômio resultante coincida com f . π:{y1,,ym}{x1,,xn,0,1}f(x1,,xn)=g(π(y1),,π(ym))yjgxi01f

Estou interessado nas (razões para) a diferença entre o polinômio permanente PER e o polinômio do ciclo hamiltoniano HAM: onde o primeiro somatório está sobre todas as permutações h : [

PERn(x)=hi=1nxi,h(i)    and    HAMn(x)=hi=1nxi,h(i)
, e o segundo é apenas sobre todasaspermutaçõescíclicas h : [ n ] [ n ] . h:[n][n]h:[n][n]
Pergunta: Por que o HAM não é uma projeção monótona PER? Ou ainda é?
Não estou pedindo provas , apenas por razões intuitivas.

Motivação: o maior limite inferior do circuito monotônico conhecido para PER (comprovado por Razborov) permanece "apenas" . Por outro lado, os resultados de Valiant implicam que CLIQUE n  é uma projeção monótona de HAM m onde CLIQUE n ( x ) = S i < j S x i , j com o somatório está sobre todos os subconjuntos S [ n ] de tamanho | S |nΩ(logn)

CLIQUEn is a monotone projection of HAMm
CLIQUEn(x)=Si<jSxi,j
S[n] . Eu mesmo não consegui obter uma redução "simples e direta" desses resultados gerais, masAlon e Boppanaafirmam (na Seção 5) que jám=25n2é suficiente para essa redução. |S|=nm=25n2

Mas espere: é sabido que o CLIQUE requer circuitos monótonos do tamanho (primeiro comprovado por Alon e Boppana usando o método de Razborov). 2nΩ(1)

Assim, foram HAM uma projecção monótona de PER, teríamos um limite inferior, também para PER. 2nΩ(1)

Na verdade, por que o HAM nem sequer é uma projeção não monótona de PER? Durante o semianel booleano, o primeiro é NP -completo, enquanto o último é em P . Mas por que? Onde é um lugar onde ser cíclico para uma permutação a torna tão especial?

PS Uma diferença óbvia poderia ser: o HAM cobre [n] por apenas um (longo) ciclo, enquanto o PER pode usar pode interromper ciclos para isso. Assim, para projetar PER para HAM, a direção mais difícil parece ser: garantir que a ausência de um ciclo hamiltoniano implique a ausência de qualquer cobertura com ciclos disjuntos no novo gráfico. É por isso que o HAM não é uma projeção de PER?

f(x)=u[n]cuiuxicu{0,1}cumm(n)2

Stasys
fonte
1
Eu tenho uma pergunta um pouco fora do tópico. Posso perguntar por que PERMANENT está em P durante o semiring booleano? Não conheço esse algoritmo.
caozhu
@caozhu: Isso ocorre simplesmente porque PERMANENTE é o mesmo que DETERMINANTE durante a semicondução booleana. O algoritmo é, então, qualquer algoritmo DETERMINANTE.
Bruno
3
{,,¬}n5/2

Respostas:

9

A seguir, uma prova sobre qualquer anel de característica zero de que o polinômio do ciclo hamiltoniano não é uma projeção monotônica de tamanho polinomial da permanente. A idéia básica é que projeções monótonas de polinômios com coeficientes não negativos levam o polítopo de Newton de um a ser uma formulação estendida do polítopo de Newton do outro e, em seguida, aplicando os limites inferiores recentes em formulações estendidas.

f(x1,,xn)g(y1,,ym)fgππgf

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
fonte
1
um argumento muito bom. Isto é exatamente o que eu procurei! De fato, formulações LP prolongadas simulam as projeções de Valiant (pelo menos monótonas).
Stasys