2
$\begingroup$

Is $⊕2SAT$ - the parity of the number of solutions of $2$-$CNF$ formulae $\oplus P$ complete?

This is listed as an open problem in Valiant's 2005 paper https://link.springer.com/content/pdf/10.1007%2F11533719.pdf. Has this been resolved?

Is there any consequence if $⊕2SAT\in P$?

$\endgroup$
8
$\begingroup$

It is shown to be $\oplus P$-complete by Faben:

https://arxiv.org/pdf/0809.1836.pdf

See Thm 3.5. Note that counting independent sets is same as counting solutions to monotone 2CNF.

$\endgroup$
  • 1
    $\begingroup$ @Turbo: the solutions of a monotone 2SAT instance of the form $F = \bigwedge_{(i,j) \in E} \neg x_i \vee \neg x_j$ are exactly the independent sets of the graph $(V,E)$ where $V = \{x_1 \ldots x_n\}$. $\endgroup$ – holf Nov 22 '17 at 20:07
  • $\begingroup$ Oh ok not max indep set. what we have is just indep set. $\endgroup$ – T.... Nov 22 '17 at 20:51

Your Answer

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

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