Numero massimo di letterali positivi in 2sat

Question

Max 2Sat è completo NP.

Invece di soddisfare il numero massimo di clausole, ho una formula 2SAT completamente soddisfatta e voglio avere il numero massimo di letterali positivi nel compito (tale che tutte le clausole siano soddisfatte, ovviamente).

Qual è la difficoltà di questo problema?

Answer 1

Questo problema è NP-Hard (e inoltre difficile da approssimare e w [1] -Hard), poiché il set massimo indipendente può essere ridotto ad esso.Riduzione: ogni variabile rappresenta un vertice e ogni clausola rappresenta un bordo.