Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
For a 3CNF $\phi$, denote by $c(\phi)$ the largest number of clauses satisfied under an assignment. Define:
$\mathrm{MAX3SAT} = \{\langle\phi, k\rangle\mid c(\phi) = k \text{ and }\phi\text{ is a 3CNF}\}$.
Prove that NP = coNP if and only if MAX3SAT is in NP.
I've been working on this forever and can't seem to figure out anything. Any help?
Let's start by describing a polytime reduction $f$ that takes a 3CNF $\varphi$ to another $f(\varphi)$ such that:
$\varphi$ is satisfiable iff $f(\varphi)$ is satisfiable.
We can always satisfy all clauses of $f(\varphi)$ but one.
The idea is very simple: add a new variable $x$, replace each clause $\alpha \lor \beta \lor \gamma$ with 3CNF clauses equivalent to $x \lor \alpha \lor \beta \lor \gamma$ (i.e. with the clauses $x \lor \alpha \lor \lnot T$, $T \lor \beta \lor \gamma$ for a new variable $T$ appearing only in these clauses), and add the clause $\lnot x$. We can always satisfy all clauses but the last by having setting $x$ and all $T$ variables to true. On the other hand, the entire 3CNF is satisfiable if and only if the original one is.
We deduce that $\varphi$ is unsatisfiable iff $c(f(\varphi)) = |f(\varphi)|-1$, where $|f(\varphi)|$ is the number of clauses in $f(\varphi)$. This shows that MAX3SAT is coNP-hard. So if MAX3SAT is in NP then NP=coNP.
Conversely, as observed by David Richerby, MAX3SAT is in the polynomial hierarchy (indeed, in $\Delta_2^P$) since $c(\varphi) = k$ iff some assignment satisfies exactly $k$ clauses, and all assignments satisfy at most $k$ clauses. If NP=coNP then the polynomial hierarchy collapses to the first level (i.e. NP), and so MAX3SAT is in NP.
