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?
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).
fonte
Respostas:
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.
fonte