<p>Deciding <span class="math-container">$2SAT$</span> is in <span class="math-container">$NL$</span> and <span class="math-container">$\#2SAT$</span> is <span class="math-container">$\#P$</span> complete while <span class="math-container">$\oplus2SAT$</span> is <span class="math-container">$\oplus P$</span> complete.
Deciding <span class="math-container">$SAT$</span>-<span class="math-container">$2$</span>-<span class="math-container">$NAE$</span> - every clause has exactly <span class="math-container">$2$</span> literals, is there an <span class="math-container">$NAE$</span> satisfying assignment to the formula - is in <span class="math-container">$Logspace$</span>.</p>
<p>What is the complexity of counting versions - <span class="math-container">$\#NAE2SAT$</span> and <span class="math-container">$\oplus NAE2SAT$</span> - of this problem?</p>

CC BY-SA 4.0
2022-02-16T23:02:50.747Z
I think you can easily rewrite every 2-NAE clause as affine clauses (e.g., $x \vee y$ is satisfied iff $x \oplus y = 1$, $x \vee \neg y$ iff $x \oplus y = 0$ etc.) thus #SAT-2-NAE can be solved in ptime (it is a linear system of $\mathbb{Z}/2\mathbb{Z}$). See Creignou, N., & Hermann, M. (1996). Complexity of generalized satisfiability counting problems. Information and computation, 125(1), 1-12.
holf
CC BY-SA 4.0
2022-02-16T23:05:43.470Z
So the complexity is $\#L$-complete?
Turbo
CC BY-SA 4.0
2022-02-19T08:01:33.737Z
I do not know, I am not that comfortable to quickly intuit results on small complexity classes. Why would you say that? What have you tried? Maybe edit the question if you are looking at something more precise than what I already commented on.
holf
<cc.complexity-theory><counting-complexity>
$\#NAE2SAT$ and $\oplus NAE2SAT$ complexity
Turbo
# $\#NAE2SAT$ and $\oplus NAE2SAT$ complexity

(Asked by: username_0 on 2022-02-16)

Deciding $2SAT$ is in $NL$ and $\#2SAT$ is $\#P$ complete while $\oplus2SAT$ is $\oplus P$ complete.
Deciding $SAT$-$2$-$NAE$ - every clause has exactly $2$ literals, is there an $NAE$ satisfying assignment to the formula - is in $Logspace$.

What is the complexity of counting versions - $\#NAE2SAT$ and $\oplus NAE2SAT$ - of this problem?

**Tags:** cc.complexity-theory, counting-complexity
> **Comments:**
> **username_1**: I think you can easily rewrite every 2-NAE clause as affine clauses (e.g., $x \vee y$ is satisfied iff $x \oplus y = 1$, $x \vee \neg y$ iff $x \oplus y = 0$ etc.) thus #SAT-2-NAE can be solved in ptime (it is a linear system of $\mathbb{Z}/2\mathbb{Z}$). See Creignou, N., & Hermann, M. (1996). Complexity of generalized satisfiability counting problems. Information and computation, 125(1), 1-12.  
> **username_0**: So the complexity is $\#L$-complete?  
> **username_1**: I do not know, I am not that comfortable to quickly intuit results on small complexity classes. Why would you say that? What have you tried? Maybe edit the question if you are looking at something more precise than what I already commented on.  

---

## 0 answers

