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.

Improve this question
$\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. 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
3
$\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.

An assignment in which $a$ is true satisfies at least $m+2$ out of the $2m+2$ 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.

Improve this answer
$\endgroup$
5
  • $\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
  • 1
    $\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
  • $\begingroup$ Why do you need to add (a or not a), isn't it enough to just add m clauses (a) not in the original m clauses? $\endgroup$
    – Anthony O
    Apr 14 '21 at 4:29
  • $\begingroup$ There could be several constructions that work. $\endgroup$
    – Yuval Filmus
    Apr 14 '21 at 6:02

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.