# SImple NP-hard proof question

$$3SATplus$$

• 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$$?

• It seems odd to assume that $3SATPLUS\in NP$ because that probably isn't true. – Tom van der Zanden Jul 14 '19 at 8:38
• 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$. – 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$$.