• Input: 2 CNF formulas $F_1$, $F_2$ where all clauses have exactly $3$ literals.

  • Question: Does every truth assignment satisfy at-least as many $F_2$ clauses as $F_1$'s?

Assume $3SATPLUS \in NP$

Prove $3SAT \leq_p$ $3SATplus$

The reduction is as follows

$F_1 = (x \lor \bar{x} \lor x) \land \dots \land (x \lor \bar{x} \lor x)$

For $n$ clauses. This means it will always accept $n$ clauses.

$F_2 = F$

This is polytime because its $2n$ clauses only $n$ more than $F$

if $F \in 3SAT$, then $F_1 = F_2$ since they both satisfy $n$ clauses so $F_1, F_2 \in 3SATplus$

I'll prove the contrapositive

If $F \notin 3SAT$, then $F_1$ satisfies $n$ clauses and $F_2$ can satisfies only up to $n-1$ so $F_1 > F_2$ always. Hence, $F_1, F_2 \notin 3SATplus$

Is there anything else left to say or does this confirm its $NP-hard$?

  • $\begingroup$ It seems odd to assume that $3SATPLUS\in NP$ because that probably isn't true. $\endgroup$ – Tom van der Zanden Jul 14 '19 at 8:38
  • $\begingroup$ The problem, as stated, is that every truth assignment must satisfy at least as many $F_2$ clauses as $F_1$ clauses. A certificate that demonstrates this is true for a single assignment is not valid. The complement problem is "there is at least one truth assignment which satisfies more $F_1$ clauses" is in $NP$, and thus this problem is in $coNP$. $\endgroup$ – Tom van der Zanden Jul 14 '19 at 11:40

If $F\in 3SAT$ it means that there is some assignment that satisfies $n$ clauses. It doesn't mean that every assignment satisfies all clauses. This makes the reduction wrong, since there might be an assignment for $F\in 3SAT$ that satisfies fewer than $n$ clauses. The reduction you've proposed would be valid if you started with $Tautology$, but then, that problem isn't known to be $NP$-complete.

Your problem is $coNP$-complete (as the reduction from $Tautology$ shows), so finding a reduction from $3SAT$ would prove $NP\subseteq coNP$.

| cite | improve this answer | |
  • $\begingroup$ Are you saying the complement of this is NP-Complete? (I think thats what CO-NP means) $\endgroup$ – bob Jul 14 '19 at 9:42
  • $\begingroup$ Yes, that is correct. $\endgroup$ – Tom van der Zanden Jul 14 '19 at 11:41
  • $\begingroup$ If I tweak this question slightly like changing it to "some truth assignment" rather than "every", would this proof be correct? $\endgroup$ – bob Jul 14 '19 at 22:26
  • $\begingroup$ Yes, but it's not really a slight change since it essentially transforms the problem to its complement. $\endgroup$ – Tom van der Zanden Jul 15 '19 at 5:26

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.