0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Sep 29 '20 at 19:22
  • $\begingroup$ 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. $\endgroup$ – DisguisedToucan Sep 29 '20 at 20:57
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I get that I need to add clauses and variables but how should these clauses be like? What's the logic? I really don't get how to check if there are at least half clauses with 3 true literals :( $\endgroup$ – DisguisedToucan Sep 29 '20 at 13:16
  • $\begingroup$ 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 ... $\endgroup$ – Pål GD Sep 29 '20 at 13:23

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.