<p>S. Cliff Liu [1] reports a deterministic algorithm for NAE-<span class="math-container">$k$</span>-SAT that is faster than the best deterministic algorithm for
<span class="math-container">$k$</span>-SAT on all <span class="math-container">$k\geq 3$</span>.</p>
<p>(Quote from Abstract)</p>
<blockquote>
<p>Our
main results include:<br />
• A deterministic algorithm for NAE-<span class="math-container">$k$</span>-SAT that is faster than the best deterministic algorithm for
<span class="math-container">$k$</span>-SAT on all <span class="math-container">$k\geq 3$</span>. Previously, no NAE-<span class="math-container">$k$</span>-SAT algorithm is known to be faster than <span class="math-container">$k$</span>-SAT
algorithms. For <span class="math-container">$k = 3$</span>, we achieve an upper bound of <span class="math-container">$1.326^n$</span>. The corresponding bound for
3-SAT is <span class="math-container">$1.328^n$</span>.<br />
...<br />
Our finding sheds new light on the following question: Is NAE-k-SAT easier than k-SAT? The answer
might be affirmative at least on solving the problems exactly and deterministically.</p>
</blockquote>
<p>See also [2] for improvements of run-time of <span class="math-container">$k$</span>-SAT.</p>
<h2>References</h2>
<p>[1] Liu, S. Cliff. &quot;The Curse and Blessing of Not-All-Equal in k-Satisfiability.&quot; arXiv preprint <a href="https://arxiv.org/abs/1809.04312" rel="nofollow noreferrer">arXiv:1809.04312</a> (2018).</p>
<p>[2] Liu, S. Cliff. &quot;Chain, generalization of covering code, and deterministic algorithm for k-sat.&quot; arXiv preprint <a href="https://arxiv.org/abs/1804.07901" rel="nofollow noreferrer">arXiv:1804.07901</a> (2018).</p>

CC BY-SA 4.0
2022-03-28T09:11:59.733Z
2022-03-29T06:42:23.887Z
2022-03-29T06:42:23.887Z
Cyriac Antony
<p>The NAE-3SAT problem is to determine whether a given 3CNF formula has a satisfying assignment that gives each clause at least one false (and at least one true) literal.
The problem is NP-complete. One can reduce 3SAT to it pretty easily so that the number of variables becomes roughly the number of clauses in the original instance, and so because of sparsification, under ETH you won't be able to get a subexponential time algorithm. (Also, it's known that NAE-SAT for unbounded length clauses requires $2^n$ time under Strong ETH.) </p>

<p>My question is, what is the best exponential time running time in terms of the number of variables?</p>

<p>There is a trivial reduction to 3SAT that does not increase the number of variables $n$ so that the fastest 3SAT algorithm has the same running time on NAE-3SAT instances (the best known is by Hertli, $1.308^n$).
Is there a faster known algorithm for NAE-3SAT than the one for 3SAT?
(Or is there a reduction that shows that the two problems are equivalent with respect to exact algorithm running times?)</p>

<p>What about monotone NAE-3SAT? Here there are no negated variables. It's known that this problem is also NP-complete. What's the fastest algorithm for it?</p>

CC BY-SA 4.0
2022-03-28T05:47:26.543Z
I suppose the following paper is your source of the statement "NAE-SAT for unbounded length clauses requires $2^n$ time under Strong ETH": Cygan et al. [**On problems as hard as CNF-SAT**](http://dx.doi.org/10.1145/2925416). Please note down any other highly relevant papers. A starting point could be of immense help to seach in the literature.
Cyriac Antony
<reference-request><exp-time-algorithms>
Exact algorithm for NAE-3SAT
virgi
# Exact algorithm for NAE-3SAT

(Asked by: username_0 on 2013-08-29)

The NAE-3SAT problem is to determine whether a given 3CNF formula has a satisfying assignment that gives each clause at least one false (and at least one true) literal.
The problem is NP-complete. One can reduce 3SAT to it pretty easily so that the number of variables becomes roughly the number of clauses in the original instance, and so because of sparsification, under ETH you won't be able to get a subexponential time algorithm. (Also, it's known that NAE-SAT for unbounded length clauses requires $2^n$ time under Strong ETH.)

My question is, what is the best exponential time running time in terms of the number of variables?

There is a trivial reduction to 3SAT that does not increase the number of variables $n$ so that the fastest 3SAT algorithm has the same running time on NAE-3SAT instances (the best known is by Hertli, $1.308^n$).
Is there a faster known algorithm for NAE-3SAT than the one for 3SAT?
(Or is there a reduction that shows that the two problems are equivalent with respect to exact algorithm running times?)

What about monotone NAE-3SAT? Here there are no negated variables. It's known that this problem is also NP-complete. What's the fastest algorithm for it?

**Tags:** reference-request, exp-time-algorithms
> **Comments:**
> **username_1**: I suppose the following paper is your source of the statement "NAE-SAT for unbounded length clauses requires $2^n$ time under Strong ETH": Cygan et al. [**On problems as hard as CNF-SAT**](http://dx.doi.org/10.1145/2925416). Please note down any other highly relevant papers. A starting point could be of immense help to seach in the literature.  

---

## 1 answers

### Answer by username_1 on 2022-03-28. Score: 2

S. Cliff Liu [1] reports a deterministic algorithm for NAE-$k$-SAT that is faster than the best deterministic algorithm for
$k$-SAT on all $k\geq 3$.

(Quote from Abstract)

> Our
> main results include:  
> • A deterministic algorithm for NAE-$k$-SAT that is faster than the best deterministic algorithm for
> $k$-SAT on all $k\geq 3$. Previously, no NAE-$k$-SAT algorithm is known to be faster than $k$-SAT
> algorithms. For $k = 3$, we achieve an upper bound of $1.326^n$. The corresponding bound for
> 3-SAT is $1.328^n$.  
> ...  
> Our finding sheds new light on the following question: Is NAE-k-SAT easier than k-SAT? The answer
> might be affirmative at least on solving the problems exactly and deterministically.

See also [2] for improvements of run-time of $k$-SAT.

## References

[1] Liu, S. Cliff. "The Curse and Blessing of Not-All-Equal in k-Satisfiability." arXiv preprint [arXiv:1809.04312](https://arxiv.org/abs/1809.04312) (2018).

[2] Liu, S. Cliff. "Chain, generalization of covering code, and deterministic algorithm for k-sat." arXiv preprint [arXiv:1804.07901](https://arxiv.org/abs/1804.07901) (2018).


---

