<p>It turns out that every opposite-read-twice formula has an even number of satisfying assignments. Here's a nice proof of it, though one could probably eliminate the graph-theoretic terminology.</p>

<p>Let $\phi$ be an opposite-read-twice CNF formula. Without loss of generality, no clause contains both a variable and its negation.</p>

<p>Consider the graph $G$ whose vertex set is the clauses of $\phi$, and for each variable $x$, we add an (undirected) edge that is incident on the two clauses containing $x$. Our WLOG assumption in $\phi$ says this graph has no self-loops. Moreover, think of labeling each edge by the variable defining it; this way we can distinguish between parallel edges.</p>

<p>An orientation of $G$ is a directed graph whose edges are formed by assigning a direction to each edge in $G$. Call an orientation of $G$ <em>admissible</em> if every vertex of $G$ has an outgoing edge. It's easy to see that satisfying assignments to $\phi$ are in bijective correspondence with admissible orientations of $G$.</p>

<p>Now I claim that the number of admissible orientations of $G$ is even. The argument is "by involution": I construct a map $\Phi$ with the following properties:</p>

<ol>
<li>$\Phi$ is totally defined (every admissible orientation is mapped somewhere)</li>
<li>$\Phi$ sends admissible orientations to admissible orientations</li>
<li>$\Phi$ is an involution ($\Phi \circ \Phi$ is the identity)</li>
<li>$\Phi$ has no fixed points</li>
</ol>

<p>Once these are established, we can observe that the orbits of $\Phi$ have size 2 and partition the admissible orientations of $G$. It follows that the number of admissible orientations is even.</p>

<p>To define $\Phi$, let $\vec{G}$ be an admissible orientation, and consider breaking $\vec{G}$ into it's strongly connected components. $\Phi$ then sends $\vec{G}$ to the orientation formed by reversing all the edges <em>within</em> the strongly connected components. The properties are then straightforwardly checked:</p>

<ol>
<li>Every directed graph can be partitioned into strongly connected components.</li>
<li>Consider the "DAG of strongly connected components" in $\vec G$; call it the quotient graph. Note that $\Phi(\vec G)$ will have the same quotient structure, since $\Phi$ doesn't affect the edges between SCCs, and strongly connected graphs remain strongly connected when reversing all their edges. Additionally, if a SCC has more than one vertex, then all its constituent vertices have an incoming edge. If an SCC has just a single vertex and isn't a source in the quotient, then all its constituent vertices have an incoming edge. So to show $\Phi(\vec G)$ is admissible, it suffices to show that the SCCs which are sources in the quotient have multiple vertices. But this follows by the fact that every vertex in the component has an incoming edge, which must come from another vertex in the component since $G$ has no self-loops and the component is a source in the quotient.</li>
<li>This follows from the fact that the quotient structure of $\Phi(\vec G)$ coincides with the quotient structure of $\vec G$.</li>
<li>By admissibility, $\vec G$ has a cycle, and hence some SCC with an edge inside it.</li>
</ol>

CC BY-SA 3.0
2016-10-26T09:02:53.993Z
Nice observation! A simpler way of seeing this (as you say, "eliminate the graph-theoretic terminology") is to observe that if an assignment a satisfies F then the assignment a'(x) = 1-a(x) satisfies F too. This can be shown easily by induction on the number of variables of F.
holf
CC BY-SA 3.0
2016-10-26T10:23:57.193Z
I don’t think $\Phi$ as given is an involution. For instance, consider the 4-element graph with directed edges $0\to1\to2\to0\to3\to1$. This is an admissible orientation. Assume its first cycle is $0\to1\to2\to0$; then, after reversing this cycle, a new cycle springs into existence, viz. $0\to3\to1\to0$. If this cycle is ordered before the original one, we are in trouble.
Emil Jeřábek
CC BY-SA 3.0
2016-10-26T10:27:04.520Z
@holf Your observation is wrong, too. Consider the CNF with clauses $x$, $\neg x\lor y\lor\neg z$, and $\neg y\lor z$. This is satisfied by the assignment $(1,1,1)$, but not by $(0,0,0)$.
Emil Jeřábek
CC BY-SA 3.0
2016-10-26T10:32:35.770Z
I think the following definition of $\Phi$ might work. Let $M$ be the set of vertices $x$ with the property that for every $y$ reachable by a (directed) path from $x$, $x$ is reachable by a path from $y$. (As a modal logician I’d describe this as the union of final clusters of the transitive reflexive closure of the directed graph, I don’t know what would graph theorists call it.) Then reverse all edges with source (hence also target) in $M$.
Emil Jeřábek
CC BY-SA 3.0
2016-10-26T13:35:00.547Z
@Emil: Ah yes, you're right. If I understand your suggestion right, you're saying break the orientation into strongly connected components and reverse the edges within components. I think this works. I'll update my answer accordingly. Thanks a lot!!
Andrew Morgan
CC BY-SA 3.0
2016-10-25T23:36:21.230Z
2016-10-26T13:58:21.880Z
2016-10-26T13:58:21.880Z
Andrew Morgan
<p>I'm not sure if my idea is understandable, so I will explain on Giorgio's example:</p>

<p>$( x_1 \lor x_2 \lor x_3 ) \land ( \lnot x_1 \lor \lnot x_3 \lor x_4 ) \land ( \lnot x_4 \lor x_5 ) \land ( \lnot x_2 \lor \lnot x_5 \lor \lnot x_6 )$. </p>

<p>First I need to change this on DNF form: </p>

<p>$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$ . </p>

<p>This should give the same answer. And no matter if I calc number of solutions modulo 2 for this:</p>

<p>$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$ = 0</p>

<p>or for this:</p>

<p>$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$ = 1 .</p>

<p>So I'm choosing the second.
I have implicants:</p>

<p>$i_0$ = $( x_1 \land x_2 \land x_3 )$</p>

<p>$i_1$ = $( \lnot x_1 \land \lnot x_3 \land x_4 )$</p>

<p>$i_2$ = $( \lnot x_4 \land x_5 )$</p>

<p>$i_3$ = $( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$</p>

<p>Now I'm building system of equations:</p>

<p>${j_0}\oplus{j_1} = 1$</p>

<p>${j_0}\oplus{j_3} = 1$</p>

<p>${j_0}\oplus{j_1} = 1$</p>

<p>${j_2}\oplus{j_3} = 1$</p>

<p>${j_3} = 1$</p>

<p>This system has one solution. 1 mod 2 = 1, so answer is 1.
But $x_6$ occurs only once. If every variable occurs two times, there is possible to have answer = 1?</p>

CC BY-SA 3.0
2016-07-27T17:38:12.633Z
If my thinking is OK, then the answer is "no". Of course I assume that variable occurs once in positive and once in negation.
Maciej
CC BY-SA 3.0
2016-07-27T17:58:43.647Z
I forgot about equation for $x_4$: ${j_1}\oplus{j_2}$ = 1. But result if the same. One solution: $j_3$ = 1, $j_2$ = 0, $j_1$ = 1, $j_0$ = 0.
Maciej
CC BY-SA 3.0
2016-07-27T17:35:49.897Z
2016-07-27T17:35:49.897Z
Maciej
<p>sorry for big delay. Until now probably the problem was solved. If not, I will present my polynomial algorithm for solving $\oplus\text{Rtw-Opp-CNF}$.
First let's try to calculate number of solutions modulo 2 of this equation:
${f(X)}\oplus{g(X)}$ .
Where f and g are logic functions and X is a vector of variables.
Common part, $f(X) \wedge g(X)$, occurs two times (one time in f(X) and one time in g(X)). So in modulo 2 common part is not important. We can calculate number of solutions modulo 2 of $f(X)$ and number of solutions modulo 2 of $g(X)$ and then sum this results modulo 2.
Now let's assume that function is presented in this form:</p>

<p>$i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$, </p>

<p>where $i_j$ is an implicant (I mean variables connected by AND operator; for example: $x_0\wedge{x_1}\wedge{\neg{x_2}}$).</p>

<p>To calculate number of solutions of this function modulo 2 we can simply calc number of solutions each implicant modulo 2 and sum all results modulo 2.
If we have vector of variables X and in implicant there is no all variables from this vector, then we know that number of solutions modulo 2 for this implicant is 0, because there is $2^k$ solutions, where k is number of missing variables.
If implicant has all variables, then number of solutions is 1 (k = 0).
So calculating number of solutions modulo 2 of $i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$ is easy.
Now let's consider:</p>

<p>$i_0\vee{i_1}\vee{i_2}\vee{...}\vee{i_{n-1}}$.</p>

<p>We know that $a\vee{b} = a\oplus{b}\oplus({a\wedge{b}})$.
In general, OR operation can be replaced by XOR of every subset of implicants connected by AND operator. 
And this is important step: we are interested in only those subsets that:</p>

<p>1) has all variables,</p>

<p>2) every variable occurs exacly one (if variable occurs two times, then we have positive and negative in one implicant, so this will give as 0).</p>

<p>Let's say that we have positive $x_0$ in implicant $i_0$ and negative $x_0$ in implicant $i_1$. Then we can write and equation: </p>

<p>${j_0}\oplus{j_1} = 1$.</p>

<p>In this equation variables ${j_0}$ and ${j_1}$ corresponds with implicants $i_0$ and $i_1$. I mean if, for example, implicant $i_0$ occurs in subset, then $j_0$ = 1. Otherwise $j_0$ = 0.
If we make this for all variables, we will get set of XOR equations and we have to calculate number of solutions of this set. This problem is easy. Number of soltions if always $2^l$, when l is some value to find.
That's all. I know that this is not formal proof, but I hope it is understandable.</p>

CC BY-SA 3.0
2016-07-27T13:07:11.933Z
Hmmm.... Is there any case when $\oplus\text{Rtw-Opp-CNF}$ = 1?
Maciej
CC BY-SA 3.0
2016-07-27T15:41:41.090Z
@AndrewMorgan But a formula with a unique clause containing all the variables exactly once would not be a read-twice formula. The restriction is *exactly* twice, not *at most* twice.
Giorgio Camerani
CC BY-SA 3.0
2016-07-27T15:51:21.137Z
@AndrewMorgan The following formula (which is not read-twice because $x_6$ appears only once) has an odd number of satisfying assignments: $( x_1 \lor x_2 \lor x_3 ) \land ( \lnot x_1 \lor \lnot x_3 \lor x_4 ) \land ( \lnot x_4 \lor x_5 ) \land ( \lnot x_2 \lor \lnot x_5 \lor \lnot x_6 )$. All the variables of such formula, except $x_6$, obey to the read-twice opposite restrictions, and the number of satisfying assignments is odd inspite the formula does not *"have a unique clause containing all the variables exactly once"*.
Giorgio Camerani
CC BY-SA 3.0
2016-07-27T16:03:28.650Z
@GiorgioCamerani I meant that among all clauses containing all the variables, there is a unique clause present in the input formula. ie in a formula like $(x_1 \vee x_2) \wedge (\bar{x_1}) \wedge (\bar{x_2})$, there is a unique clause with all the variables present once, while in $(x_1 \vee x_2) \wedge (\bar{x_1} \vee \bar{x_2})$ or $(x_1) \wedge (\overline{x_1}) \wedge (x_2) \wedge (\overline{x_2})$ there is not. I didn't mean to exclude the presence of other clauses in the input. But in any case I think I was misunderstanding Maciej's answer, so I deleted my previous comment.
Andrew Morgan
CC BY-SA 3.0
2016-07-27T16:27:58.013Z
@AndrewMorgan OK, now I see. However consider that also in the family of cases you meant, the number of satisfying assignments seems to remain even. The question posed by Maciej in his comment turns out to be challenging.
Giorgio Camerani
CC BY-SA 3.0
2016-07-27T17:02:01.747Z
Maciej's system of equations can be expressed as $Mj = 1$. Note that $M$ has a nontrivial kernel (the all-ones vector is inside it). This means that $Mj = 1$ either has no solutions or at least 2 solutions. (If $j$ is a solution, then $j + 1$ is also a solution.) In particular, there cannot be a unique solution, and it follows that the number of solutions (and hence satisfying assignments) is always even. Is there a simpler way to come to the same conclusion?
Andrew Morgan
CC BY-SA 3.0
2016-07-27T12:08:55.423Z
2016-07-27T12:08:55.423Z
Maciej
<p>In a read-twice opposite CNF formula each variable appears twice, once positive and once negative.</p>

<p>I'm interested in the $\oplus\text{Rtw-Opp-CNF}$ problem, which consists in computing the parity of the number of satisfying assignments of a read-twice opposite CNF formula.</p>

<p>I was unable to find any reference about the complexity of such problem. The closest I was able to find is that the counting version $\#\text{Rtw-Opp-CNF}$ is $\#\text{P}$-complete (see section 6.3 in <a href="http://pages.cs.wisc.edu/~jyc/papers/interpolation08.pdf" rel="nofollow">this paper</a>).</p>

<p>Thanks in advance for your help.</p>

<hr>

<p><strong>Update 10th April 2016</strong></p>

<ul>
<li>In <a href="https://books.google.it/books?id=8I8ECAAAQBAJ&amp;pg=PA3&amp;lpg=PA3&amp;dq=readtwiceoppositesat&amp;source=bl&amp;ots=FWTMKbn9Ev&amp;sig=ubyMUmIZo0awDlYM-IGTyFRU1c8&amp;hl=it&amp;sa=X&amp;ved=0ahUKEwjissTkzITMAhVMVRQKHe81AL8Q6AEIHzAA#v=onepage&amp;q=readtwiceoppositesat&amp;f=false" rel="nofollow">this paper</a>, the $\oplus\text{Rtw-Opp-SAT}$ problem is shown to be $\oplus\text{P}$-complete, however the formula produced by reduction from $3\text{SAT}$ is not in CNF, and as soon as you try to convert it back into CNF you get a read-thrice formula.</li>
<li>The monotone version $\oplus\text{Rtw-Mon-CNF}$ is shown to be $\oplus\text{P}$-complete in <a href="http://people.seas.harvard.edu/~valiant/focs06.pdf" rel="nofollow">this paper</a>. In such paper, $\oplus\text{Rtw-Opp-CNF}$ is quickly mentioned at the end of section 4: Valiant says it is degenerate. It is not clear to me what being degenerate exactly means, nor what does it imply in terms of hardness.</li>
</ul>

<hr>

<p><strong>Update 12th April 2016</strong></p>

<p>It would be also very interesting to know if anyone has ever studied the complexity of the $\Delta\text{Rtw-Opp-CNF}$ problem. Given a read-twice opposite CNF formula, such problem asks to compute 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. I've not found any literature about it.</p>

<hr>

<p><strong>Update 29th May 2016</strong></p>

<p>As pointed out by Emil Jeřábek in his comment, it is not true that Valiant said that the problem $\oplus\text{Rtw-Opp-CNF}$ is degenerate. He only said that a more restricted version of such problem, $\oplus\text{Pl-Rtw-Opp-3CNF}$, is degenerate. In the meanwhile, I continue to not know what degenerate exactly means, but at least now it seems clear that it is a synonym of lack of expressive power.</p>

CC BY-SA 3.0
2016-05-20T08:35:09.560Z
I can't find a mention of ⊕Rtw-Opp-CNF in Valiant's paper. He claims that ⊕Pl-Rtw-Opp-3CNF is "degenerate", but that involves several additional restrictions.
Emil Jeřábek
CC BY-SA 3.0
2016-05-29T13:53:22.657Z
@EmilJeřábek: You are definitely right. I was misleaded by my ignorance of the meaning of _"degenerate"_, and I applied the same sort of reasoning that is normally applied in presence of completeness results: if a certain problem is complete for some class, removing restrictions from it obviously preserves completeness. Even if I still do not know what _"degenerate"_ exactly means, it is at least clear to me now that such term is somehow a synonym of weakness (i.e. lack of expressive power), hence the aforementioned reasoning cannot be applied. I've corrected the question accordingly.
Giorgio Camerani
CC BY-SA 3.0
2016-05-29T15:46:56.940Z
@Maciej: Really? How does your polynomial algorithm work?
Giorgio Camerani
CC BY-SA 3.0
2016-08-27T04:05:04.717Z
This seems like search an arbitrary problem. Why do you, or why should anyone, care?
Sasho Nikolov
CC BY-SA 3.0
2016-08-29T19:40:07.817Z
@SashoNikolov I do not understand your comment, could you please clarify? Are you saying that the problems mentioned here are uninteresting?
Giorgio Camerani
<cc.complexity-theory><ds.algorithms><counting-complexity>
Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)
Giorgio Camerani
# Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)

(Asked by: username_0 on 2016-04-07)

In a read-twice opposite CNF formula each variable appears twice, once positive and once negative.

I'm interested in the $\oplus\text{Rtw-Opp-CNF}$ problem, which consists in computing the parity of the number of satisfying assignments of a read-twice opposite CNF formula.

I was unable to find any reference about the complexity of such problem. The closest I was able to find is that the counting version $\#\text{Rtw-Opp-CNF}$ is $\#\text{P}$-complete (see section 6.3 in [this paper](http://pages.cs.wisc.edu/~jyc/papers/interpolation08.pdf)).

Thanks in advance for your help.

---

**Update 10th April 2016**

* In [this paper](https://books.google.it/books?id=8I8ECAAAQBAJ&pg=PA3&lpg=PA3&dq=readtwiceoppositesat&source=bl&ots=FWTMKbn9Ev&sig=ubyMUmIZo0awDlYM-IGTyFRU1c8&hl=it&sa=X&ved=0ahUKEwjissTkzITMAhVMVRQKHe81AL8Q6AEIHzAA#v=onepage&q=readtwiceoppositesat&f=false), the $\oplus\text{Rtw-Opp-SAT}$ problem is shown to be $\oplus\text{P}$-complete, however the formula produced by reduction from $3\text{SAT}$ is not in CNF, and as soon as you try to convert it back into CNF you get a read-thrice formula.
* The monotone version $\oplus\text{Rtw-Mon-CNF}$ is shown to be $\oplus\text{P}$-complete in [this paper](http://people.seas.harvard.edu/~valiant/focs06.pdf). In such paper, $\oplus\text{Rtw-Opp-CNF}$ is quickly mentioned at the end of section 4: Valiant says it is degenerate. It is not clear to me what being degenerate exactly means, nor what does it imply in terms of hardness.

---

**Update 12th April 2016**

It would be also very interesting to know if anyone has ever studied the complexity of the $\Delta\text{Rtw-Opp-CNF}$ problem. Given a read-twice opposite CNF formula, such problem asks to compute 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. I've not found any literature about it.

---

**Update 29th May 2016**

As pointed out by Emil Jeřábek in his comment, it is not true that Valiant said that the problem $\oplus\text{Rtw-Opp-CNF}$ is degenerate. He only said that a more restricted version of such problem, $\oplus\text{Pl-Rtw-Opp-3CNF}$, is degenerate. In the meanwhile, I continue to not know what degenerate exactly means, but at least now it seems clear that it is a synonym of lack of expressive power.

**Tags:** cc.complexity-theory, ds.algorithms, counting-complexity
> **Comments:**
> **username_1**: I can't find a mention of ⊕Rtw-Opp-CNF in Valiant's paper. He claims that ⊕Pl-Rtw-Opp-3CNF is "degenerate", but that involves several additional restrictions.  
> **username_0**: @EmilJeřábek: You are definitely right. I was misleaded by my ignorance of the meaning of _"degenerate"_, and I applied the same sort of reasoning that is normally applied in presence of completeness results: if a certain problem is complete for some class, removing restrictions from it obviously preserves completeness. Even if I still do not know what _"degenerate"_ exactly means, it is at least clear to me now that such term is somehow a synonym of weakness (i.e. lack of expressive power), hence the aforementioned reasoning cannot be applied. I've corrected the question accordingly.  
> **username_0**: @Maciej: Really? How does your polynomial algorithm work?  
> **username_2**: This seems like search an arbitrary problem. Why do you, or why should anyone, care?  
> **username_0**: @SashoNikolov I do not understand your comment, could you please clarify? Are you saying that the problems mentioned here are uninteresting?  

---

## 3 answers

### Answer by username_3 on 2016-10-25. Score: 3

It turns out that every opposite-read-twice formula has an even number of satisfying assignments. Here's a nice proof of it, though one could probably eliminate the graph-theoretic terminology.

Let $\phi$ be an opposite-read-twice CNF formula. Without loss of generality, no clause contains both a variable and its negation.

Consider the graph $G$ whose vertex set is the clauses of $\phi$, and for each variable $x$, we add an (undirected) edge that is incident on the two clauses containing $x$. Our WLOG assumption in $\phi$ says this graph has no self-loops. Moreover, think of labeling each edge by the variable defining it; this way we can distinguish between parallel edges.

An orientation of $G$ is a directed graph whose edges are formed by assigning a direction to each edge in $G$. Call an orientation of $G$ *admissible* if every vertex of $G$ has an outgoing edge. It's easy to see that satisfying assignments to $\phi$ are in bijective correspondence with admissible orientations of $G$.

Now I claim that the number of admissible orientations of $G$ is even. The argument is "by involution": I construct a map $\Phi$ with the following properties:

1. $\Phi$ is totally defined (every admissible orientation is mapped somewhere)
2. $\Phi$ sends admissible orientations to admissible orientations
3. $\Phi$ is an involution ($\Phi \circ \Phi$ is the identity)
4. $\Phi$ has no fixed points

Once these are established, we can observe that the orbits of $\Phi$ have size 2 and partition the admissible orientations of $G$. It follows that the number of admissible orientations is even.

To define $\Phi$, let $\vec{G}$ be an admissible orientation, and consider breaking $\vec{G}$ into it's strongly connected components. $\Phi$ then sends $\vec{G}$ to the orientation formed by reversing all the edges *within* the strongly connected components. The properties are then straightforwardly checked:

1. Every directed graph can be partitioned into strongly connected components.
2. Consider the "DAG of strongly connected components" in $\vec G$; call it the quotient graph. Note that $\Phi(\vec G)$ will have the same quotient structure, since $\Phi$ doesn't affect the edges between SCCs, and strongly connected graphs remain strongly connected when reversing all their edges. Additionally, if a SCC has more than one vertex, then all its constituent vertices have an incoming edge. If an SCC has just a single vertex and isn't a source in the quotient, then all its constituent vertices have an incoming edge. So to show $\Phi(\vec G)$ is admissible, it suffices to show that the SCCs which are sources in the quotient have multiple vertices. But this follows by the fact that every vertex in the component has an incoming edge, which must come from another vertex in the component since $G$ has no self-loops and the component is a source in the quotient.
3. This follows from the fact that the quotient structure of $\Phi(\vec G)$ coincides with the quotient structure of $\vec G$.
4. By admissibility, $\vec G$ has a cycle, and hence some SCC with an edge inside it.

> **Comments:**
> **username_4**: Nice observation! A simpler way of seeing this (as you say, "eliminate the graph-theoretic terminology") is to observe that if an assignment a satisfies F then the assignment a'(x) = 1-a(x) satisfies F too. This can be shown easily by induction on the number of variables of F.  
> **username_1**: I don’t think $\Phi$ as given is an involution. For instance, consider the 4-element graph with directed edges $0\to1\to2\to0\to3\to1$. This is an admissible orientation. Assume its first cycle is $0\to1\to2\to0$; then, after reversing this cycle, a new cycle springs into existence, viz. $0\to3\to1\to0$. If this cycle is ordered before the original one, we are in trouble.  
> **username_1**: @holf Your observation is wrong, too. Consider the CNF with clauses $x$, $\neg x\lor y\lor\neg z$, and $\neg y\lor z$. This is satisfied by the assignment $(1,1,1)$, but not by $(0,0,0)$.  
> **username_1**: I think the following definition of $\Phi$ might work. Let $M$ be the set of vertices $x$ with the property that for every $y$ reachable by a (directed) path from $x$, $x$ is reachable by a path from $y$. (As a modal logician I’d describe this as the union of final clusters of the transitive reflexive closure of the directed graph, I don’t know what would graph theorists call it.) Then reverse all edges with source (hence also target) in $M$.  
> **username_3**: @Emil: Ah yes, you're right. If I understand your suggestion right, you're saying break the orientation into strongly connected components and reverse the edges within components. I think this works. I'll update my answer accordingly. Thanks a lot!!  

---

### Answer by username_5 on 2016-07-27. Score: 0

I'm not sure if my idea is understandable, so I will explain on Giorgio's example:

$( x\_1 \lor x\_2 \lor x\_3 ) \land ( \lnot x\_1 \lor \lnot x\_3 \lor x\_4 ) \land ( \lnot x\_4 \lor x\_5 ) \land ( \lnot x\_2 \lor \lnot x\_5 \lor \lnot x\_6 )$.

First I need to change this on DNF form:

$( x\_1 \land x\_2 \land x\_3 ) \lor ( \lnot x\_1 \land \lnot x\_3 \land x\_4 ) \lor ( \lnot x\_4 \land x\_5 ) \lor ( \lnot x\_2 \land \lnot x\_5 \land \lnot x\_6 )$ .

This should give the same answer. And no matter if I calc number of solutions modulo 2 for this:

$( x\_1 \land x\_2 \land x\_3 ) \lor ( \lnot x\_1 \land \lnot x\_3 \land x\_4 ) \lor ( \lnot x\_4 \land x\_5 ) \lor ( \lnot x\_2 \land \lnot x\_5 \land \lnot x\_6 )$ = 0

or for this:

$( x\_1 \land x\_2 \land x\_3 ) \lor ( \lnot x\_1 \land \lnot x\_3 \land x\_4 ) \lor ( \lnot x\_4 \land x\_5 ) \lor ( \lnot x\_2 \land \lnot x\_5 \land \lnot x\_6 )$ = 1 .

So I'm choosing the second.
I have implicants:

$i\_0$ = $( x\_1 \land x\_2 \land x\_3 )$

$i\_1$ = $( \lnot x\_1 \land \lnot x\_3 \land x\_4 )$

$i\_2$ = $( \lnot x\_4 \land x\_5 )$

$i\_3$ = $( \lnot x\_2 \land \lnot x\_5 \land \lnot x\_6 )$

Now I'm building system of equations:

${j\_0}\oplus{j\_1} = 1$

${j\_0}\oplus{j\_3} = 1$

${j\_0}\oplus{j\_1} = 1$

${j\_2}\oplus{j\_3} = 1$

${j\_3} = 1$

This system has one solution. 1 mod 2 = 1, so answer is 1.
But $x\_6$ occurs only once. If every variable occurs two times, there is possible to have answer = 1?

> **Comments:**
> **username_5**: If my thinking is OK, then the answer is "no". Of course I assume that variable occurs once in positive and once in negation.  
> **username_5**: I forgot about equation for $x_4$: ${j_1}\oplus{j_2}$ = 1. But result if the same. One solution: $j_3$ = 1, $j_2$ = 0, $j_1$ = 1, $j_0$ = 0.  

---

### Answer by username_5 on 2016-07-27. Score: -1

sorry for big delay. Until now probably the problem was solved. If not, I will present my polynomial algorithm for solving $\oplus\text{Rtw-Opp-CNF}$.
First let's try to calculate number of solutions modulo 2 of this equation:
${f(X)}\oplus{g(X)}$ .
Where f and g are logic functions and X is a vector of variables.
Common part, $f(X) \wedge g(X)$, occurs two times (one time in f(X) and one time in g(X)). So in modulo 2 common part is not important. We can calculate number of solutions modulo 2 of $f(X)$ and number of solutions modulo 2 of $g(X)$ and then sum this results modulo 2.
Now let's assume that function is presented in this form:

$i\_0\oplus{i\_1}\oplus{i\_2}\oplus{...}\oplus{i\_{n-1}}$,

where $i\_j$ is an implicant (I mean variables connected by AND operator; for example: $x\_0\wedge{x\_1}\wedge{\neg{x\_2}}$).

To calculate number of solutions of this function modulo 2 we can simply calc number of solutions each implicant modulo 2 and sum all results modulo 2.
If we have vector of variables X and in implicant there is no all variables from this vector, then we know that number of solutions modulo 2 for this implicant is 0, because there is $2^k$ solutions, where k is number of missing variables.
If implicant has all variables, then number of solutions is 1 (k = 0).
So calculating number of solutions modulo 2 of $i\_0\oplus{i\_1}\oplus{i\_2}\oplus{...}\oplus{i\_{n-1}}$ is easy.
Now let's consider:

$i\_0\vee{i\_1}\vee{i\_2}\vee{...}\vee{i\_{n-1}}$.

We know that $a\vee{b} = a\oplus{b}\oplus({a\wedge{b}})$.
In general, OR operation can be replaced by XOR of every subset of implicants connected by AND operator.
And this is important step: we are interested in only those subsets that:

1) has all variables,

2) every variable occurs exacly one (if variable occurs two times, then we have positive and negative in one implicant, so this will give as 0).

Let's say that we have positive $x\_0$ in implicant $i\_0$ and negative $x\_0$ in implicant $i\_1$. Then we can write and equation:

${j\_0}\oplus{j\_1} = 1$.

In this equation variables ${j\_0}$ and ${j\_1}$ corresponds with implicants $i\_0$ and $i\_1$. I mean if, for example, implicant $i\_0$ occurs in subset, then $j\_0$ = 1. Otherwise $j\_0$ = 0.
If we make this for all variables, we will get set of XOR equations and we have to calculate number of solutions of this set. This problem is easy. Number of soltions if always $2^l$, when l is some value to find.
That's all. I know that this is not formal proof, but I hope it is understandable.

> **Comments:**
> **username_5**: Hmmm.... Is there any case when $\oplus\text{Rtw-Opp-CNF}$ = 1?  
> **username_0**: @AndrewMorgan But a formula with a unique clause containing all the variables exactly once would not be a read-twice formula. The restriction is *exactly* twice, not *at most* twice.  
> **username_0**: @AndrewMorgan The following formula (which is not read-twice because $x_6$ appears only once) has an odd number of satisfying assignments: $( x_1 \lor x_2 \lor x_3 ) \land ( \lnot x_1 \lor \lnot x_3 \lor x_4 ) \land ( \lnot x_4 \lor x_5 ) \land ( \lnot x_2 \lor \lnot x_5 \lor \lnot x_6 )$. All the variables of such formula, except $x_6$, obey to the read-twice opposite restrictions, and the number of satisfying assignments is odd inspite the formula does not *"have a unique clause containing all the variables exactly once"*.  
> **username_3**: @GiorgioCamerani I meant that among all clauses containing all the variables, there is a unique clause present in the input formula. ie in a formula like $(x_1 \vee x_2) \wedge (\bar{x_1}) \wedge (\bar{x_2})$, there is a unique clause with all the variables present once, while in $(x_1 \vee x_2) \wedge (\bar{x_1} \vee \bar{x_2})$ or $(x_1) \wedge (\overline{x_1}) \wedge (x_2) \wedge (\overline{x_2})$ there is not. I didn't mean to exclude the presence of other clauses in the input. But in any case I think I was misunderstanding Maciej's answer, so I deleted my previous comment.  
> **username_0**: @AndrewMorgan OK, now I see. However consider that also in the family of cases you meant, the number of satisfying assignments seems to remain even. The question posed by Maciej in his comment turns out to be challenging.  
> **username_3**: Maciej's system of equations can be expressed as $Mj = 1$. Note that $M$ has a nontrivial kernel (the all-ones vector is inside it). This means that $Mj = 1$ either has no solutions or at least 2 solutions. (If $j$ is a solution, then $j + 1$ is also a solution.) In particular, there cannot be a unique solution, and it follows that the number of solutions (and hence satisfying assignments) is always even. Is there a simpler way to come to the same conclusion?  

---

