1
$\begingroup$

I've been struggling lately with a problem that was in my last complex algorithms exam, and I can't find a solution. The problem is as follows:

Half-SAT is a problem where C is a CNF boolean formula with n variables and m clauses, where m is even. We have to determine if there exists an interpretation that satisfies exactly half of the clauses. Prove Half-SAT intractability with a reduction from SAT.

Clues: A formula can have duplicated clauses It's possible to write clauses that are always true.

I'd be very grateful if you could give me any clue on how to approach this problem.

| cite | improve this question | |
$\endgroup$
  • $\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. The site tends to work better if you can identify a concept you're having trouble understanding. See here for a relevant discussion. $\endgroup$ – D.W.♦ Aug 28 '15 at 16:35
  • $\begingroup$ I googled reductions from any problem to any other just to get used to reductions, I read chapters 9.5-9.8 from "The Algorithm Design Manual" of Skiena as my teacher recommended, looked for courses on coursera or anywhere I could find and searched long about any similar problem. The problem was that I had my mind working on the clauses composition and I couldn't think of anything new, I needed a new approach on the problem and my mind was stuck. Yuval Filmus answered, but if you have any book/lecture recommended to help me in the future, I'd be very grateful. $\endgroup$ – valarion Aug 28 '15 at 18:45
1
$\begingroup$

The clue that you got is a bit strange, since true clauses are not enough. Here is one possible solution. Given a CNF formula with $m$ clauses, let $a$ be a new variable, add the clause $a \lor \lnot a$, and add $m+1$ copies of the clause $a$. I claim that if this formula is half-satisfiable then the original formula is satisfiable.

Indeed, an assignment in which $a$ is true satisfies at least $m+2$ out of the $2m+4$ clauses, which is more than half the clauses. Therefore any assignment half-satisfying the new formula must assign false to $a$, leading to the conclusion that the $m$ original clauses must all be satisfied.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! I've been focusing this problem wrong since the beginning. After reading reductions from SAT and 3-SAT, I was trying to reduce each clause independently and then join all together, and lost global vision. $\endgroup$ – valarion Aug 28 '15 at 15:49
  • $\begingroup$ There are 2m + 2 total clauses though, right? Not 2m + 4. Ie, m orig + 1 (a or not a) + (m+1, just a) = m + 1 + m + 1 = 2m + 2. Then if a is false, m+1 are false, the a or not a 1 is true, and iff the orig m are satisfiable, then m+1 are satisfiable which is 1/2 of 2m + 2. $\endgroup$ – DragonMoon Mar 19 '18 at 18:56
  • $\begingroup$ Presumably a variant of this construction does work. You can edit my answer to fix it once you find such a variant. $\endgroup$ – Yuval Filmus Mar 19 '18 at 20:10

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.