Kernel polinomial para

10

O problema parametrizado do k-FLIP SAT é definido como:

Entrada: uma fórmula 3-CNF com n variáveis ​​e uma atribuição de verdade σ : [ n ] { 0 , 1 } Parâmetro: k Pergunta: podemos transformar a atribuição σ em uma atribuição satificante σ para φ inverter o valor de verdade de no máximo k variáveis?φnσ:[n]{0,1}
k
σσφ k

O problema está claramente no FPT ( Stefan Szeider: A complexidade parametrizada da pesquisa local k-Flip para SAT e MAX SAT. Otimização discreta 8 (1): 139-145 (2011) )

Ele admite um núcleo polinomial? (sob premissas razoáveis ​​de complexidade)

As técnicas recentes de composição cruzada (consulte Hans L. Bodlaender, Bart MP Jansen, Stefan Kratsch, "Limites inferiores da kernelização por composição cruzada" ) parecem inúteis para esse problema. E também parecem inúteis para problemas semelhantes que perguntam se uma determinada solução para um problema difícil de NP pode ser encontrada a partir de uma determinada instância por pesquisa local (limitando a pesquisa aos vizinhos da instância em questão, sob alguma medida de distância natural).

Marzio De Biasi
fonte
Legal, mas por que esse problema é claramente FPT? Se você o fizer 2-CNF com exatamente k inversões de variável em vez de no máximo, acredito que o problema é equivalente a fpt-k-clique. Eu tenho trabalhado em um artigo que inclui alguns resultados sobre problemas exatos do k-flip.
Michael Wehar
Eu acho que dizer que está no FPT significa que é solucionável em . f(k)nO(1)
Michael Wehar
Acho que dizer que é no meio XP que é solucionável no tempo. nf(k)
precisa saber é o seguinte
Não sei a relação entre o problema exato do k-flip e o problema no máximo do k-flip. Inicialmente, pensei que você estava dizendo que o problema do atmost-k-flip é mais fácil no sentido de que o atmost-k-flip é FPT. Eu digo mais fácil, porque exato-k-flip não pode ser FPT, a menos que ETH seja falso. A razão para isto é porque é equivalente a k-clique e sabe-se que algoritmos de tempo para k-clique implicam ETH é falsa. f(k)nO(1)
Michael Wehar
11
@ MichaelWehar: ops, você está certo (eu excluo o comentário errado), a questão precisa ser polida (eu defini o problema como "no máximo k FLIPS"). O mais rápido possível Vou dar uma olhada no (s) artigo (s) (um deles deve ser Stefan Szeider, "A complexidade parametrizada da pesquisa local do k-Flip para SAT e MAX SAT") em que se diz que o k-FLIP SAT é FPT para cláusulas com tamanho delimitado.
Marzio De Biasi

Respostas:

12

O problema não possui um núcleo polinomial, a menos que o NP esteja em coNP / poli. A técnica de composição cruzada de nosso artigo se aplica de maneira não trivial.

(G1,k),(G2,k),,(Gt,k)knkO(k+logt)kkt

Givi,1,vi,2,,vi,nuii[t]Gi{vi,x,vi,y}Gi(vi,xvi,y¬ui)iuisão configurados como false, para que todas essas cláusulas sejam atendidas. Para criar o comportamento OR na composição, aumentaremos a fórmula para garantir que uma atribuição satisfatória ajuste pelo menos um seletor para true e, em seguida, também forme uma cobertura de vértice do gráfico selecionado.

ttlogt1tiuiixyz(¬xyz)(x(yz))x

k(k+logt+1)kGik

GikkkuiilogtiGiiiuiGi

k+logt+1uiui1+logtuiGi¬uiGi1+logtkkGi

Bart Jansen
fonte
11
Este artigo traz consequências mais fortes dessa compressão.
Obrigado!!! (Eu imediatamente removi o "et al." Da referência ;-). Prova agradável (IMO, você deve publicá-la em um documento).
Marzio De Biasi