Núcleo polinómico para

El problema parametrizado de k-FLIP SAT se define como:

Entrada: una fórmula 3-CNF $\varphi$ con $n$ variables y una asignación de verdad $\sigma : [n] \to \{0,1\}$
Parámetro: $k$
Pregunta: ¿podemos transformar la asignación $\sigma$ en una asignación de saturación $\sigma'$ para $\varphi$ cambiar el valor de verdad de a lo sumo $k$ variables?

El problema está claramente en FPT ( Stefan Szeider: La complejidad parametrizada de k-Flip Local Search para SAT y MAX SAT. Optimización discreta 8 (1): 139-145 (2011) )

¿Admite un núcleo polinomial? (bajo supuestos de complejidad razonables)

Las técnicas recientes de composición cruzada (ver Hans L. Bodlaender, Bart MP Jansen, Stefan Kratsch, "Kernelization Lower Bounds By Cross-Composition" ) parecen inútiles para este problema. Y también parecen inútiles para problemas similares que preguntan si se puede encontrar una solución dada a un problema NP-difícil a partir de una instancia dada mediante búsqueda local (limitando la búsqueda a los vecinos de la instancia dada, bajo alguna medida de distancia natural).

El problema no tiene un núcleo polinomial a menos que NP esté en coNP / poly. La técnica de composición cruzada de nuestro artículo se aplica de manera no trivial.

Permítame mostrarle cómo el clásico problema de la cubierta de vértices O-cross-composes en el problema k-FLIP-SAT; por los resultados en el documento citado, esto es suficiente. Concretamente, construimos un algoritmo de tiempo polinómico cuya entrada es una secuencia de instancias de cobertura de vértices que comparten el mismo valor de k y todos tener exactamente n vértices. La salida es una instancia de k -FLIP SAT con un valor de parámetro de O ( k $(G_1,k), (G_2, k), \ldots, (G_t, k)$$k$$n$$k$ , que es lo suficientemente pequeño para una composición cruzada, de modo que lainstancia de k -FLIP SAT tiene respuesta yes si uno de los gráficos de entrada tiene una cubierta de vértice de tamaño k . Al duplicar una entrada (que no cambia el valor del OR) podemos asegurarnos de que el número de entradas t sea ​​una potencia de dos.$O(k + \log t)$$k$$k$$t$

La composición procede de la siguiente manera. Numere los vértices en el gráfico de cada gráfico de entrada como v i , 1 , v i , 2 , ... , v i , n . Haga una variable correspondiente en la instancia de FLIP-SAT para cada vértice de cada gráfico de entrada. Además, haga una variable de selección u i para cada número de instancia de entrada i ∈ [ t ] . Para cada gráfico de entrada G i , agregamos algunas cláusulas a la fórmula. Para cada borde { v i , $G_i$$v_{i,1}, v_{i,2}, \ldots, v_{i,n}$$u_i$$i \in [t]$$G_i$ del gráfico G i , agregue la cláusula ( v i , x ∨ v i , y ∨ ¬ u i ) a la fórmula, que codificará "cualquiera de los puntos finales de este borde se establece en verdadero, o la instancia i no está activa ". En la asignación inicial, todas las variables de vértice se establecen en falso y todas las variables de selección u $\{v_{i,x}, v_{i,y}\}$$G_i$$(v_{i,x} \vee v_{i,y} \vee \neg u_i)$$i$$u_i$se establecen en falso, de modo que todas estas cláusulas se cumplan. Para construir el comportamiento OR en la composición, aumentaremos la fórmula para asegurarnos de que una asignación satisfactoria establezca al menos un selector en verdadero, y luego también debe formar una cubierta de vértice del gráfico seleccionado.

Para asegurarnos de que podemos hacer esta selección manteniendo la distancia de volteo pequeña en comparación con el número de entradas , utilizamos la estructura de un árbol binario completo con t hojas, que tiene un registro de altura t . Número las hojas de 1 a T y asociar el i hoja -ésimo con la variable u i que los controles si la entrada i está activo o no. Cree una nueva variable para cada nodo interno del árbol binario. Para cada nodo interno, deje que su variable correspondiente sea xy las variables de sus dos hijos sean y y z . Agregar la cláusula $t$$t$$\log t$$1$$t$$i$$u_i$$i$$x$$y$$z$ a la fórmula que captura la implicación ( x → ( y ∨ z ) ) , haciendo cumplir que x solo puede ser verdadero si uno de sus hijos es verdadero. Para completar la fórmula, agregue una cláusula singleton que diga que la variable del nodo raíz del árbol binario debe ser verdadera. En la asignación de verdad inicial, los valores de todas las variables para los nodos internos se establecen en falso, lo que satisface todas las cláusulas de la fórmula, excepto la cláusula singleton que requiere que el nodo raíz del árbol tenga su variable verdadero.$(\neg x \vee y \vee z)$$(x \rightarrow (y \vee z))$$x$

Esto completa la descripción de la fórmula y la asignación de la verdad. Establezca el parámetro del problema FLIP DISTANCE para que sea igual a ( k + log t + 1 ) , que está adecuadamente limitado para una composición cruzada. Queda por demostrar que podemos voltear las variables k ' para hacer que la fórmula sea verdadera si algún gráfico de entrada G i tiene una cubierta de vértice de tamaño k .$k'$$(k + \log t + 1)$$k'$$G_i$$k$

En la dirección inversa, suponga que tiene una cubierta de vértice de tamaño k . Establezca las k variables correspondientes a los k vértices en la portada como verdaderas volteándolas. Establezca la variable del selector u i en verdadero para codificar que la entrada i está activada, y voltee las variables de los nodos del árbol binario interno log t en la ruta de la hoja i a la raíz en verdadero. Es fácil verificar que esta es una asignación satisfactoria: las implicaciones en el árbol binario están todas satisfechas, el valor del nodo raíz se establece en verdadero, las cláusulas que verifican los bordes de G i ' para $G_i$$k$$k$$k$$u_i$$i$$\log t$$i$$G_{i'}$ quedo satisfecho porque u i ' permanece falso, mientras que las cláusulas de gráfico G i son satisfechas porque por cada borde nos propusimos al menos un punto final a verdadero.$i' \neq i$$u_{i'}$$G_i$

Para la dirección hacia adelante, suponga que la fórmula puede satisfacerse volteando como máximo variables. Luego debemos voltear la variable del nodo raíz a verdadero. Las implicaciones en el árbol binario obligan a que al menos una variable del selector de una hoja se establezca como verdadera, digamos u i . Para satisfacer las implicaciones codificadas en el árbol binario, todos los nodos internos en la ruta desde u i a la raíz se establecieron en verdadero, lo que representa 1 + log t flips. Como u i está establecido en verdadero, las cláusulas hechas para el gráfico G i no están satisfechas en el literal$k + \log t + 1$$u_i$$u_i$$1 + \log t$$u_i$$G_i$ , por lo que están satisfechos porque uno de los puntos finales de cada borde de G i está establecido en verdadero. Dado que al menos 1 + log t variables del árbol binario se voltearon, a lo sumo k las variables de vértice se voltean a verdadero en esta solución. Esto codifica una cubierta de vértice de tamaño k en G i y demuestra que una de las entradas es una instancia SÍ. Esto completa la prueba.$\neg u_i$$G_i$$1 + \log t$$k$$k$$G_i$