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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.