2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ What did you try? Where did you get stuck? Did you see that it's enough to prove that MAX3SAT is co-NP-complete? $\endgroup$ – David Richerby Dec 8 '14 at 1:29
  • $\begingroup$ I see how that would be enough, but I thought the MAX3SAT problem was NP complete, not co np complete? Even the wikipedia page states the decision problem version of it is np complete. I'm just confused about this question in general :/ $\endgroup$ – Matt Grant Dec 8 '14 at 1:42
  • 3
    $\begingroup$ Most sources just seem to say "MAX3SAT is the problem of finding an assignment that satisfies the maximum number of clauses; the decision version is NP-complete", without bothering to define the decision version. I suspect they're talking about the problem "Is there an assignment that satisfies at least $k$ clauses?", whereas you're dealing with "Is the maximum exactly $k$?" That's equivalent to "Can you satisfy $k$ clauses but not satisfy $k-1$?"; the "but not" part is suggestive of co-NP. $\endgroup$ – David Richerby Dec 8 '14 at 1:48
1
$\begingroup$

Let's start by describing a polytime reduction $f$ that takes a 3CNF $\varphi$ to another $f(\varphi)$ such that:

  1. $\varphi$ is satisfiable iff $f(\varphi)$ is satisfiable.

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

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