MAX 2-SAT is polynomial time reducible to 2-SAT?

Question

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.

Answer 1

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.