Número máximo de literais positivos em 2sat

Question

max 2sat é NP completo.

Em vez de satisfazer o número máximo de cláusulas, tenho uma fórmula de 2sat totalmente satisfatória e quero ter o número máximo de literais positivos na tarefa (tal que todas as cláusulas estejam satisfeitas, é claro).

Qual é a dificuldade desse problema?

Answer 1

Esse problema é NP-HARD (e, além disso, é difícil aproximar e W [1] -Hard), porque o máximo de conjunto independente pode ser reduzido a ele.Redução: Cada variável representa um vértice e cada cláusula representa uma borda.