<p>The <span class="math-container">$\oplus P$</span>-completeness of <span class="math-container">$\oplus$</span>2SAT was resolved much earlier than Faben's preprint in 2008: it was resolved by Valiant himself in 2006. See</p>
<blockquote>
<p>Leslie G. Valiant:
Accidental Algorithms. FOCS 2006: 509-517
<a href="https://ieeexplore.ieee.org/document/4031386" rel="nofollow noreferrer">https://ieeexplore.ieee.org/document/4031386</a></p>
</blockquote>
<p>A link with no paywall: <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.3342" rel="nofollow noreferrer">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.3342</a></p>
<p>Showing therefore that <span class="math-container">$\oplus$</span>2SAT <span class="math-container">$\in P$</span> would imply that <span class="math-container">$P = \oplus P$</span>, which further implies (by the usual proof of Toda's theorem) that the entire polynomial hierarchy is in <span class="math-container">$BPP$</span>. This seems extremely unlikely!</p>

CC BY-SA 4.0
2021-01-28T07:50:13.330Z
Faben’s paper is from 2008, not 2018.
Emil Jeřábek
CC BY-SA 4.0
2021-01-28T15:40:13.993Z
Thanks, maybe I need new glasses :)
Ryan Williams
CC BY-SA 4.0
2021-01-28T16:37:04.293Z
I think both your glasses are working fine: in https://arxiv.org/abs/0809.1836, the date at center top is 2018, but the arxiv timestamp on the vertical left is 2008.
Giorgio Camerani
CC BY-SA 4.0
2021-01-28T16:56:30.820Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-01-28T19:59:29.527Z
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...
Giorgio Camerani
CC BY-SA 4.0
2021-01-27T22:53:59.023Z
2021-01-28T15:39:42.353Z
2021-01-28T15:39:42.353Z
Ryan Williams
<p>There are <span class="math-container">$2$</span> possible further reductions in addition to Faben's one, to show <span class="math-container">$\oplus P$</span>-completeness of <span class="math-container">$\oplus 2$</span>-SAT.</p>
<p>First reduction is from <span class="math-container">$\oplus$</span>CNF-SAT to (not necessarily monotone) <span class="math-container">$\oplus 2$</span>-SAT, as follows: replace each clause <span class="math-container">$c = \{\ell_1, \cdots, \ell_k\}$</span> in the original instance with a set of <span class="math-container">$k$</span> clauses <span class="math-container">$c_1 = \{\lnot u, \lnot\ell_1\}, \cdots, c_k = \{\lnot u, \lnot\ell_k\}$</span>, where <span class="math-container">$u$</span> is a fresh new variable. I like to call such operation as <em>clause rotation</em>. Each time you <em>rotate</em> a clause, the parity of the number of satisfying assignments stays unaltered. Actually it is more than that: the <em>difference</em> 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 <span class="math-container">$\oplus 2$</span>-SAT instance which is not monotone (unless so was the original instance), and which has only <span class="math-container">$n + m$</span> variables (while in Faben's reduction the resulting monotone <span class="math-container">$\oplus 2$</span>-SAT instance had <span class="math-container">$3n + m$</span> variables).</p>
<p>Second reduction is from <span class="math-container">$\oplus$</span>CNF-SAT to monotone <span class="math-container">$\oplus 2$</span>-SAT, like Faben's but again with less variables. You create a graph with <span class="math-container">$n + m$</span> nodes: <span class="math-container">$n$</span> nodes for the variables and <span class="math-container">$m$</span> 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 <span class="math-container">$2$</span> 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).</p>

CC BY-SA 4.0
2021-01-28T19:49:52.890Z
2021-01-28T19:49:52.890Z
Giorgio Camerani
<p>It is shown to be <span class="math-container">$\oplus P$</span>-complete by Faben:</p>
<p><a href="https://arxiv.org/abs/0809.1836" rel="nofollow noreferrer">https://arxiv.org/abs/0809.1836</a></p>
<p>See Thm 3.5. Note that counting independent sets is same as counting solutions to monotone 2CNF.</p>

CC BY-SA 3.0
2017-11-22T20:07:47.873Z
@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\}$.
holf
CC BY-SA 3.0
2017-11-22T20:51:52.510Z
Oh ok not max indep set. what we have is just indep set.
Turbo
CC BY-SA 4.0
2017-11-22T19:27:27.350Z
2021-01-28T07:48:28.403Z
2021-01-28T07:48:28.403Z
Heng Guo
<p>Is $⊕2SAT$ - the parity of the number of solutions of $2$-$CNF$ formulae $\oplus P$ complete?</p>

<p>This is listed as an open problem in Valiant's 2005 paper <a href="https://link.springer.com/content/pdf/10.1007%2F11533719.pdf" rel="noreferrer">https://link.springer.com/content/pdf/10.1007%2F11533719.pdf</a>. Has this been resolved?</p>

<p>Is there any consequence if $⊕2SAT\in P$?</p>

<counting-complexity>
$⊕P$-completeness of $⊕2SAT$
Turbo
# $⊕P$-completeness of $⊕2SAT$

(Asked by: username_0 on 2017-11-22)

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

**Tags:** counting-complexity

---

## 3 answers

### Answer by username_4 on 2017-11-22. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_5**: @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\}$.  
> **username_0**: Oh ok not max indep set. what we have is just indep set.  

---

### Answer by username_1 on 2021-01-27. Score: 7

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!

> **Comments:**
> **username_2**: Faben’s paper is from 2008, not 2018.  
> **username_1**: Thanks, maybe I need new glasses :)  
> **username_3**: I think both your glasses are working fine: in https://arxiv.org/abs/0809.1836, the date at center top is 2018, but the arxiv timestamp on the vertical left is 2008.  
> **username_2**: 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.  
> **username_3**: 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...  

---

### Answer by username_3 on 2021-01-28. Score: 0

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).


---

