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$
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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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