Algum resultado no CSP booleano binário além da rastreabilidade de parâmetros fixos do problema quase 2SAT?

Seja uma fórmula 2CNF um número inteiro não negativo. Está provado neste artigo que o problema de decidir se é possível excluir no máximo cláusulas para tornar satisfatório é um parâmetro fixo tratável, onde é o parâmetro. Minha pergunta é se há algum trabalho que generalize esse resultado para outro CSP booleano binário? (Ou seja, decidir se é possível excluir no máximo restrições para tornar satisfatória uma instância de CSP, parametrizada por ) Ou quaisquer resultados negativos? $\varphi$ $k$ $k$ $\varphi$ $k$ $k$ $k$

parameterized-complexity csp fixed-parameter-tractable Regularidade
fonte

Estou realmente curioso para saber o que estou perdendo aqui - não é quase 2SAT trivialmente parametrizável tratável, porque existem apenas polinomialmente muitos conjuntos de no máximo cláusulas para fixo ?

k

$k$

k

$k$

21711 Dave

@Dave existem cerca de conjuntos de cláusulas, mas a rastreabilidade de parâmetros fixos não permite que apareça na parte exponencial do tempo de execução.

O (n^{k})

$O(n^k)$

k

$k$

Regularidade

Respostas:

Para meu conhecimento, classificar essa variante do CSP está totalmente aberto. Você pode expressar alguns problemas rastreáveis de parâmetros fixos na configuração (por exemplo, d-Hitting Set é aproximadamente o caso em que você tem cláusulas positivas de tamanho no máximo d mais atribuições negativas; aproximadamente significa que o problema de CSP é um pouco mais geral, mas reduz facilmente de volta ao d-HS, ou pelo menos d-HS ponderado). Mesmo para as restrições que você pode implementar por meio de fórmulas 2-CNF existencialmente quantificadas, fica aberto qual é a complexidade. O problema é que, ao implementar restrições dessa maneira, enquanto elas são 2-CNF, você paga apenas uma para excluir a coisa toda. Portanto, mesmo restrições simples que são apenas a conjunção de duas outras podem ser difíceis (posso ter exemplo + referência posteriormente).

Stefan Kratsch
fonte