What is complexity class for #XOR-2-SAT? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-17T23:07:47Z https://cs.stackexchange.com/feeds/question/79880 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/79880 3 What is complexity class for #XOR-2-SAT? rus9384 https://cs.stackexchange.com/users/71879 2017-08-09T13:15:07Z 2017-08-09T19:07:36Z <p>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.</p> <p>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}$?</p> <p>Assuming that answer is given as $2^k$, where $k\in\{0,\mathbb{N}\}$, where $k$ is number of connected components. Otherwise we'd need polynomial space to print the number.</p>