# 3SAT to 3SAT-WITH-MAJORITY reduction

I've been struggling with reduction while solving this exercise and I would really appreciate some help if not the solution.

Problem: [3-SAT-WITH-MAJORITY]

Input: A set of clauses $$C = {\{c_1, \dots, c_k}\}$$ over $$n$$ boolean variables $$x_1, \dots, x_n$$ where every clause contains exactly three literals.

Output: YES if there is a truth assignment to the variable such that both

• every clause is satisfied under the assignment
• there are at least k/2 clauses in which all 3 literals are set to true under the assignment.

NO otherwise.

Show that this problem is NP-complete.

• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. "Here is my exercise, please solve it for me" questions often aren't of much use to others.
– D.W.
Sep 29 '20 at 19:22
• I'm trying to understand the logic behind this reduction, I get the theory but I just don't understand what the new clauses should look like and I feel like that WILL help me understand the concept in order to apply it to new problems. Sep 29 '20 at 20:57

Hint: Take a SAT instance $$C$$ with $$k$$ clauses and introduce $$3k$$ new variables $$\top^i_1, \top^i_2, \top^i_3$$ for $$i \leq k$$ and construct $$k$$ new clauses $$c^\top_i = \{ \top^i_1,\top^i_1,\top^i_3 \}$$. Let $$C' = C \cup \bigcup_{i=1}^k c^\top_i$$ be the input to 3SAT-WITH-MAJORITY.
• You can just assume all $\top^i_j$ are set to true. Then these $k$ clauses have only true literals. No, suppose that 3SAT-WITH-MAJORITY was polynomial time solvable, then in the original instance you can just drop the new clauses ... Sep 29 '20 at 13:23