Sea una fórmula 2CNF yk un número entero no negativo. En este documento se demuestra que el problema de decidir si uno puede eliminar a lo sumo k cláusulas para hacer φ satisfactorio, es manejable con parámetros fijos, donde k es el parámetro. Mi pregunta es si hay algún trabajo que generalice este resultado a otro CSP booleano binario. (Es decir, para decidir si uno puede eliminar a lo sumo k restricciones para hacer que alguna instancia de CSP sea satisfactoria, parametrizada por k ) ¿O algún resultado negativo?
parameterized-complexity
csp
fixed-parameter-tractable
Regularidad
fuente
fuente
Respuestas:
Que yo sepa, la clasificación de esta variante CSP está abierta. Puede expresar algunos problemas manejables de parámetros fijos en la configuración (por ejemplo, d-Hitting Set es aproximadamente el caso en el que tiene cláusulas de tamaño positivas en la mayoría de las asignaciones negativas d plus; aproximadamente significa que el problema de CSP es un poco más general pero se reduce fácilmente volver a d-HS, o al menos d-HS ponderado). Incluso para las restricciones que puede implementar a través de fórmulas 2-CNF cuantificadas existencialmente, está abierto cuál es la complejidad. El problema es que al implementar restricciones de esta manera, mientras son 2-CNF, solo paga uno para eliminar todo. Por lo tanto, incluso las restricciones simples que son solo la conjunción de otras dos pueden ser difíciles (puedo tener un ejemplo + referencia más adelante).
fuente