2
$\begingroup$

I know that 2-SAT is solvable in polynomial time and 2-SAT is NP-Hard.

I have issue about this statement: MAX 2-SAT is polynomial-time reducible to 2-SAT. Can you explain to me how reduction looks like? I need the only intution about that, but not proof.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

I think there is some confusion here. MAX-2-SAT is NP-Hard (and its decision version is NP-Complete), while 2-SAT is in P and hence also in NP. This means that 2-SAT is polynomial-time reducible to (the decision version of) MAX-2-SAT. The converse is not true unless P=NP.

Let $\phi$ be a 2-SAT formula with $m$ clauses. If you really want to reduce an instance $\phi$ of 2-SAT to (the decision version of) MAX-2-SAT, then this simply amounts to checking whether at least $m$ (i.e., all) clauses of $\phi$ are satisfiable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.