What is complexity class for #XOR-2-SAT?

Question

I know that given problem is in $\mathsf{FP}$: if given formula is satisfiable, then it is only needed to find out how many connected components equality (undirected) graph has. In fact problem is to count the amount of connected components.

However, is it possible to solve it using only log space? Is then the given problem is $\mathsf{FL}$-complete? Or, maybe, this problem is complete somewhere in $\mathsf{AC}$?

Answer 1

The given problem is in $\mathsf {FL}$:

1. Solve if it is satisfiable. Let the result be number $s$. Can be done in logarithmic space.
2. Set $t=0$.
3. Count the number of clauses of form $(a\oplus \overline a)$ where $a$ does not appear in any other clause except clauses identical to that one. For each such clause increase $t$ by $1$.

Step 3 can be performed in log space as follows:

for every i in V:
    flagIndependent = true
    flagAppears = false
    for every j in C:
        if C_j isIdentical(`(x_i xor not(x_i))`):
            flagAppears = true
        elseif C_j contains(`x_i`):
            flagIndependent = false
    t += flagAppears * flagIndependent

Two variables i and j take space $\log(|V|)$ and $\log(|C|)$ respectively. Variables flagIndependent and flagAppears take $1$ bit each. Functions checking clauses also require $O(\log(n))$ space at most. Therefore the total space used is logarithmic.

The answer is $s2^t$.