8
$\begingroup$

Not All Equal SAT is an NP Complete problem. Let us now consider another variant of the problem.

Given a Not All Equal SAT (NAESAT) problem (arbitrary number of literals allowed per clause) with an additional constraint that each pair of clauses share at least 1 literal (not variables but literals).

Is this problem still NP-hard? It seems so, but I am unsure about the reduction.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ The usual rule is one question per post. $\endgroup$
    – Yuval Filmus
    Commented Jun 26, 2017 at 15:34
  • 1
    $\begingroup$ Agreed. I thought they were too similar for two separate questions (one a more generalized form of another). Will take care next time onward. $\endgroup$
    – TheoryQuest1
    Commented Jun 26, 2017 at 15:59
  • $\begingroup$ Please ask only one question per post. This is for your own benefit, as well as the benefit of others with the same question -- as it stands, this post will now be treated by the site as "answered", even though the second of your questions isn't addressed by the answer below. I've edited the post to remove your second question. You can post it separately; you can find the deleted text by looking at the revision history (click 'edited'). $\endgroup$
    – D.W. ♦
    Commented Jun 27, 2017 at 21:22

1 Answer 1

Reset to default
9
$\begingroup$

Your problem is NP-hard, as can be seen by a (known, I believe) reduction from CNF-SAT: Reduce from (for example) $3$-SAT as follows. Given a formula $F$, create a formula for your special NAE-SAT by introducing exactly one additional variable, say $y$. Add $y$ to every clause in $F$ to obtain $F'$.

Example: $F = (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_2 \vee x_3 \vee \neg x_4)$ becomes $F' := (x_1 \vee x_2 \vee \neg x_3 \vee y) \wedge (\neg x_2 \vee x_3 \vee \neg x_4 \vee y)$

After doing this, every clause contains $y$ and thus shares (at least) one literal.

Proof sketch: If $F$ is satisfiable, use the same satisfying assignment to satisfy $F'$, together with $y = false$.

If $F'$ is satisfiable, there are two options

  • $y = false $, in this case the same assignment satisfies $F$ ($F'$ has at least one true literal per clause, and it is never $y$, thus $F$ has at least one true literal per clause as well)
  • $y = true$, negate the satifying assignment for $F'$ to satisfy $F$ (at least one false literal per clause in $F'$, after negating the assignment we have at least one true literal per clause)
Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. It seems fine. The second one i too am thinking about. I am thinking in terms of graph theory. Either clauses and vertices as graph nodes and a problem on bipartite graphs. Or perhaps another problem on a graphs about path or tree. But no concrete clue yet. $\endgroup$
    – TheoryQuest1
    Commented Jun 26, 2017 at 16:11
  • $\begingroup$ Let us know if you find a solution $\endgroup$
    – user53923
    Commented Jun 27, 2017 at 14:38
  • 1
    $\begingroup$ surely will. No success yet. $\endgroup$
    – TheoryQuest1
    Commented Jun 27, 2017 at 15:34

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.