1
$\begingroup$

We call a Boolean formula beautiful if it is CNF and if every clause either contains only positive literals or only negative literals. For example, the Boolean formula:

$$ (x_1 \vee x_2) \wedge (\neg x_2 \vee \neg x_3 \vee \neg x_4) \wedge (\neg x_1 \vee \neg x_4) \wedge (x_1 \vee x_4 \vee x_5 \vee x_6) \wedge (\neg x_5)$$

is a beautiful Boolean formula. Now the question is how can we prove that the problem of finding a satisfying assignment of a beautiful Boolean formula is NP-hard? We call this problem BEAUTIFUL-SAT.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ It seems you have already figured it out. So what is the question? $\endgroup$
    – Emil Jeřábek
    Commented Nov 13 at 15:26
  • $\begingroup$ I guess I'm worried I have a bug in my reasoning somewhere. This is only the second reduction proof I have attempted to do so I figured I'd ask the cs community how this problem can be proved formally. I put my attempt so I can show my current understanding of the problem so people can point out where I'm wrong. $\endgroup$
    – dkm
    Commented Nov 13 at 16:13
  • $\begingroup$ Well, your argument is correct. $\endgroup$
    – Emil Jeřábek
    Commented Nov 13 at 17:21

1 Answer 1

Reset to default
3
$\begingroup$

We start with an arbitrary 3-CNF formula $f$. We take as an example:

$$ f = (\neg x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_2 \vee x_4) \wedge (x_1 \vee x_3 \vee x_4) $$

Now we define for every negated literal $\neg x_k \Leftrightarrow x_{k + n}$ with $n$ the number of literals in $f$. We then replace all negated literals with their non-negated counterparts, which we can do in linear time. For the example we then get:

$$ f = (x_5 \vee x_6 \vee x_3) \wedge (x_5 \vee x_2 \vee x_4) \wedge (x_1 \vee x_3 \vee x_4) $$

And we get $f$ in a beautiful form. Now we have the constraints $\neg x_k \Leftrightarrow x_{k + n}$ or equivalently $(x_k \vee x_{k + n}) \wedge (\neg x_k \vee \neg x_{k + n})$. Adding these constraints to $f$ we get:

$$g = f \wedge (x_1 \vee x_5) \wedge (\neg x_1 \vee \neg x_5) \wedge (x_2 \vee x_6) \wedge (\neg x_2 \vee \neg x_6)$$

The constraints can be added in linear time. Now we have that $f$ has been made into a beautiful formula and the additional constraints can also be made beautiful and so $g$ is beautiful. And so we have started from an arbitrary 3-CNF formula and reduced it to an equivalent beautiful formula in polynomial time. This concludes the proof.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.