22
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. Please note down any other highly relevant papers. A starting point could be of immense help to seach in the literature. $\endgroup$
    – Cyriac Antony
    Mar 28, 2022 at 5:47

1 Answer 1

Reset to default
2
$\begingroup$

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 (2018).

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

Improve this answer
$\endgroup$

Your Answer

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

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