6
$\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$?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
10
$\begingroup$

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

https://arxiv.org/abs/0809.1836

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

Improve this answer
$\endgroup$
2
  • 3
    $\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
    Commented Nov 22, 2017 at 20:07
  • $\begingroup$ Oh ok not max indep set. what we have is just indep set. $\endgroup$
    – Turbo
    Commented Nov 22, 2017 at 20:51
7
$\begingroup$

The $\oplus P$-completeness of $\oplus$2SAT was resolved much earlier than Faben's preprint in 2008: it was resolved by Valiant himself in 2006. See

Leslie G. Valiant: Accidental Algorithms. FOCS 2006: 509-517 https://ieeexplore.ieee.org/document/4031386

A link with no paywall: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.3342

Showing therefore that $\oplus$2SAT $\in P$ would imply that $P = \oplus P$, which further implies (by the usual proof of Toda's theorem) that the entire polynomial hierarchy is in $BPP$. This seems extremely unlikely!

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Faben’s paper is from 2008, not 2018. $\endgroup$
    – Emil Jeřábek
    Commented Jan 28, 2021 at 7:50
  • $\begingroup$ Thanks, maybe I need new glasses :) $\endgroup$
    – Ryan Williams
    Commented Jan 28, 2021 at 15:40
  • 1
    $\begingroup$ I think both your glasses are working fine: in arxiv.org/abs/0809.1836, the date at center top is 2018, but the arxiv timestamp on the vertical left is 2008. $\endgroup$
    – Giorgio Camerani
    Commented Jan 28, 2021 at 16:37
  • 2
    $\begingroup$ Yeah, the date in the pdf file shows 2018. Arxiv just uses regular LaTeX, thus unless the author overrides \date in the file, it will show the date it was compiled. This is often the date of submission, when the file is first processed, and the resulting pdf is cached. But an older paper may drop out of the cache, in which case it is compiled anew the next time someone requests the pdf, resulting in a completely different date. All in all, this is just another of the many reasons why it is a stupid idea to directly link to a pdf of a paper instead of to an informative meta page. $\endgroup$
    – Emil Jeřábek
    Commented Jan 28, 2021 at 16:56
  • $\begingroup$ Yes, exactly. It happened to me once, and emitting a new version of a paper only to correct the date is not a good idea either, as the center top date would correctly go back in time, but the timestamp on the vertical left would switch from the past to the present... $\endgroup$
    – Giorgio Camerani
    Commented Jan 28, 2021 at 19:59
0
$\begingroup$

There are $2$ possible further reductions in addition to Faben's one, to show $\oplus P$-completeness of $\oplus 2$-SAT.

First reduction is from $\oplus$CNF-SAT to (not necessarily monotone) $\oplus 2$-SAT, as follows: replace each clause $c = \{\ell_1, \cdots, \ell_k\}$ in the original instance with a set of $k$ clauses $c_1 = \{\lnot u, \lnot\ell_1\}, \cdots, c_k = \{\lnot u, \lnot\ell_k\}$, where $u$ is a fresh new variable. I like to call such operation as clause rotation. Each time you rotate a clause, the parity of the number of satisfying assignments stays unaltered. Actually it is more than that: the difference between the number of satisfying assignments having an odd number of variables set to true and the number of satisfying assignments having an even number of variables set to true stays unaltered. After having rotated every original clause (each time using a different fresh new variable of course), you end up with a $\oplus 2$-SAT instance which is not monotone (unless so was the original instance), and which has only $n + m$ variables (while in Faben's reduction the resulting monotone $\oplus 2$-SAT instance had $3n + m$ variables).

Second reduction is from $\oplus$CNF-SAT to monotone $\oplus 2$-SAT, like Faben's but again with less variables. You create a graph with $n + m$ nodes: $n$ nodes for the variables and $m$ nodes for the clauses. There is an edge between a variable node and a clause node if and only if such variable is mentioned in such clause. There is an edge between $2$ clause nodes if and only if there is a variable which is mentioned positive in one and negative in the other. The parity of the number of independent sets of such graph is the same as the parity of the number of satisfying assignments of the original formula. But here the savings in variables had a price: the aforementioned odd-even difference is not preserved in this reduction (whereas Faben's reduction preserves it).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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