Decision variation of max sat

Question

I am trying to prove that following decison variation of MaxSAT is both NP hard and co-NP hard. $(\phi ,k) \in L$ iff an assignment of $\phi$ satisfies k clauses and no assignment satisfies more than k clauses.

I think we can show that NP hardness by reducing SAT to L by setting k=m (number of clauses). But I can't reduce $\overline{SAT}$ to L. Is that reduction possible?

Answer 1

Given a $\overline{SAT}$ instance $\psi$ with $m$ clauses, let $\phi$ be the formula formed by adding to each clause a new variable $x$ (the same for all clauses), and a new clause $\bar{x}$. If $\psi$ is satisfiable then $\phi$ is satisfiable, whereas if $\psi$ is unsatisfiable then the maximum number of clauses that can be satisfied is $m$.