Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)

Question

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

Thanks in advance for your help.

---

Update 10th April 2016

• In this paper, 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. 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.

Answer 1

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.

Answer 2

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?

Answer 3

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.