According to Wikipedia, while the 2SAT problem is polynomial, its maximization variant MAX2SAT is NP-hard. But, they do not provide a reference for this claim. Is this obvious? If not, where can I find the reduction used to prove this claim?
$\begingroup$
$\endgroup$
2
asked Nov 21, 2018 at 11:34
-
1$\begingroup$ Try formulating independent set problem as a max 2SAT problem. $\endgroup$– xskxzrNov 21, 2018 at 12:20
-
$\begingroup$ Thanks! I found the original proof here: sciencedirect.com/science/article/pii/0304397576900591 in pages 4-6. $\endgroup$– Erel Segal-HaleviNov 21, 2018 at 13:10
Add a comment
|