# Computational Complexity of Not All Equal SAT variant

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.

• The usual rule is one question per post. – Yuval Filmus Jun 26 '17 at 15:34
• Agreed. I thought they were too similar for two separate questions (one a more generalized form of another). Will take care next time onward. – TheoryQuest1 Jun 26 '17 at 15:59
• 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'). – D.W. Jun 27 '17 at 21:22

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)
• 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. – TheoryQuest1 Jun 26 '17 at 16:11
• Let us know if you find a solution – user53923 Jun 27 '17 at 14:38
• surely will. No success yet. – TheoryQuest1 Jun 27 '17 at 15:34