Weird exceptions

Some say Computational Complexity is all about the $1$-million worth question $$\mathsf{P} \overset{?}{=} \mathsf{NP}$$ Of course, this is far from being correct. There are many more complexity classes and many more models of computation. Technically, the two classes $\mathsf{P}$ and $\mathsf{NP}$ are not special. But they are of special interest, since they pose a barrier between what perhaps can be computed on our classical computers in a feasible amount of time and those problems that in many cases would require an exponential amount of time. Or, spoken in a more simple way, they show up the barrier between what can be computed and what can not be computed due resource constraints.

However, there are some problems that have some weird special cases, which seem to be missed accidentally by the claws of the $\mathsf{NP}$ monster and fell into the lower class of $\mathsf{P}$. Both examples are actual based on the beautiful work of Leslie Valiant who showed how to connect the problem to count satisfying assignments to counting perfect matchings in planar graphs. The first one is:

$\#_2$ $\mathsf{PL}$-$\mathsf{RTW}$-$\mathsf{MON}$-$3\mathsf{CNF}$ vs. $\#_7$ $\mathsf{PL}$-$\mathsf{RTW}$-$\mathsf{MON}$-$3\mathsf{CNF}$

The term PL-RTW-MON-3CNF stands for

PLANAR-READTWICE-MONOTONE-3CONJUNCTIVENORMALFORM.

and is a special type of boolean formula.

1. PLANAR: The incidence graph of the formula is planar
2. READTWICE: Each literal occurs at most twice
3. MONOTONE: Each literal only occurs in its positive form, i.e., there is no $-x_i$.
4. 3CONJUNCTIVENORMALFORM: A formula in CNF with 3 literals per clause

The hashtag in front means that the number of solution to such a formula is counted, and the subscript, e.g., #$_p$ means that we "only" have to compute the number of solution modulo $p$. For $p=2$, this is often called the parity problem and is also denoted as $\otimes$PL-RTW-MON-3CNF.  So, with #$_2$ and #$_7$ we have to compute the solutions modulo $2$ and modulo $7$. And surprisingly, one of them is $\mathsf{NP}$-hard and the other one is in $\mathsf{P}$. Ok, and if you have to guess you probably would guess that from modulo $7$ you get more information, hence probably it is the harder one, right?

But that is not the case, computing the solutions modulo $7$ is the easy case, whereof the parity version is hard. The reason for this is actually that the following system of equations:
\begin{align*}
u_1 &\equiv x_1x_2x_3 \pmod{p}\\
u_2 &\equiv x_1x_3 \pmod{p}\\
u_3 &\equiv x_2x_3 \pmod{p}\\
u_4 &\equiv x_3 \pmod{p}\\
0 &\equiv u_1n_{1}n_{2}n_0 + u_2n_1n_3n_2 + u_3n_3n_2n_1 + u_4n_3n_3n_3 \pmod{p}\\
1 &\equiv u_1n_{1}n_{2}p_0 + u_2n_1n_3p_2 + u_3n_3n_2p_1 + u_4n_3n_3p_3 \pmod{p}\\
1 &\equiv u_1n_{1}p_{2}n_0 + u_2n_1p_3n_2 + u_3n_3p_2n_1 + u_4n_3p_3n_3 \pmod{p}\\
1 &\equiv u_1n_{1}p_{2}p_0 + u_2n_1p_3p_2 + u_3n_3p_2p_1 + u_4n_3p_3p_3 \pmod{p}\\
1 &\equiv u_1p_{1}n_{2}n_0 + u_2p_1n_3n_2 + u_3p_3n_2n_1 + u_4p_3n_3n_3 \pmod{p}\\
1 &\equiv u_1p_{1}n_{2}p_0 + u_2p_1n_3p_2 + u_3p_3n_2p_1 + u_4p_3n_3p_3 \pmod{p}\\
1 &\equiv u_1p_{1}p_{2}n_0 + u_2p_1p_3n_2 + u_3p_3p_2n_1 + u_4p_3p_3n_3 \pmod{p}\\
1 &\equiv u_1p_{1}p_{2}p_0 + u_2p_1p_3p_2 + u_3p_3p_2p_1 + u_4p_3p_3p_3 \pmod{p}\\
\end{align*} For $x_i, n_i, p_i \in \mathbb{F}_p$, it can be solved for $p=7$ but not for $p=2$.

So the fact that this equation system can be solved over some field $\mathbb{F}_p$ or not separates the two major complexity classes $\mathsf{NP}$ and $\mathsf{P}$ (for this type of formula) which looks really just accidental.
Why the validity of these equations lead to a polynomial time algorithm for #$_7$ PL-RTW-MON-3CNF, one has to understand holographic algorithms [1,2] and matchgates (i.e. a weighted undirected planar graph) and how they utilize the FKT algorithm in a clever way.
On the other hand, isn't a beautiful result that two complexity classes can be separated by the simple but really convincing fact that a certain system of equation can not be solved, e.g., only over the integers or certain fields? Remark that also the two classes Linear Programming and Integer Linear Programming have a similar property. The former can be solved efficiently also in the worst case where the later is known to be NP-hard.


Furthermore, there are relationships between two things, that seem really strange but are based on the fact, that otherwise some complexity classes would be equal that are not suspected to be so. One of such things is:

Valiant's 0/1-XOR-gadgets can not have a circular planar BDC

To understand why this is a strange behaviour, i have to explain this in a bit more detail. An $0$/$1$-XOR-gadget is a small graph $\mathcal{G}$ with $n > 4$ vertices and with two input nodes $i_1$ and $i_2$ and two output nodes $o_1$ and $o_2$, and each edge has weight $1$. If you take the adjacency matrix $M$ of that gadget, then these four nodes define the following submatrices:
\begin{align*}
M, M^{i_1,i_2}_{o_1,o_2}, M^{i_1}_{o_1}, M^{i_2}_{o_2}, M^{i_1}_{o_2}, M^{i_2}_{o_1}
\end{align*}, whereof $M^{i_1,...,i_k}_{o_1,...,o_k}$ means the submatrix that arises when removing columns $i_1$ to $i_k$ and rows $o_1$ to $o_k$.

Next, compute the permanent of those submatrices. Since the dimension of these matrices can be rather small, we can assume that this will be fast enough for practical purposes.
\begin{align*}
\mathsf{perm}(M) = r_1 \\
\mathsf{perm}(M^{i_1,i_2}_{o_1,o_2}) = r_2 \\
\mathsf{perm}(M^{i_1}_{o_1}) = r_3 \\
\mathsf{perm}(M^{i_2}_{o_2}) = r_4 \\
\mathsf{perm}(M^{i_1}_{o_2}) = r_5 \\
\mathsf{perm}(M^{i_2}_{o_2}) = r_6 \\
\end{align*} Next, build the BDC, i.e., the bipartite double cover, of the graph. That is the graph which corresponds to the following adjacency matrix $$\mathsf{BDC}(\mathcal{G}) = \begin{pmatrix} 0 & M\\ M^t & 0 \end{pmatrix}$$
The number of vertices doubles in $\mathsf{BDC}(\mathcal{G})$, it is loop-free and undirected. Next, test if there exists a circular planar embedding of the BDC graph, with the nodes \begin{align*}
 \hat{i}_1 = n+i_1,\; \hat{i}_2 = n+i_2,\; o_1, \;o_2
\end{align*}
on the boundary. For clarity, a circular planar embedding of a graph according to a given boundary, is a planar embedding whereof the specified boundary nodes are on the outside, i.e., can be connected to other graphs without destroying the planarity.

If you run a computer program to find such a gadget via brute force, you will immediatelly find some graphs that match all these criteria. In Figure 1 you can see an example of such a gadget. 

Figure 1 - The graph $\mathcal{G}$ on the left with $o_1 = 1, i_1 = 3, o_2 = 6, i_2 = 4$ and its BDC on the right. The BDC is circular planar according to the nodes $o_1 = 1, i_1 + 6 = 9, o_2 = 6$ and $i_2 + 6 = 10$.

But to make such graphs a valid $0$/$1$-XOR-gadget, that can be used to count the number of solutions of some boolean formula modulo a prime $p > 2$, it must further hold:
\begin{align*}
\mathsf{perm}(M) \equiv r_1 \equiv 0\pmod{p} \\
\mathsf{perm}(M^{i_1,i_2}_{o_1,o_2}) = r_2 \equiv 0\pmod{p}\\
\mathsf{perm}(M^{i_1}_{o_1}) = r_3 \not\equiv 0\pmod{p}\\
\mathsf{perm}(M^{i_2}_{o_2}) = r_4 \not\equiv 0\pmod{p}\\
\mathsf{perm}(M^{i_1}_{o_2}) = r_5 \equiv 0\pmod{p}\\
\mathsf{perm}(M^{i_2}_{o_2}) = r_6 \equiv 0\pmod{p}\\
\end{align*}
The gadget from Figure 1 does not fulfill the set of permanent-equations from above, hence it has a circular planar embedding according to the correct nodes.  However, finding such a gadget whenever $(r_1,r_2,r_3,r_4,r_5,r_6) = (0,0,\neq 0, \neq 0,0,0) \pmod{p}$ is impossible. Because in that case you could actually do something "useful" with that gadget. In Figure 2 you can see a $0$/$1$-XOR-gadget with the values $$(r_1,r_2,r_3,r_4,r_5,r_6) \equiv (0,0,1,2,0,0)\pmod{3}$$.

Figure 2 - This gadget has the correct signature $(0,0,1,2,0,0) \pmod{3}$ and is thus a valid 0/1-XOR-gadget input 1 nodes 2 and output nodes 3 and 4.

In Figure 3 you can see the bipartite double cover of it. You can not find a circular planar embedding with the boundary nodes 8,9,3 and 4 because of the signature of the graph from Figure 2 being a correct XOR signature. You can even find a graph that has 3 of the 4 nodes on the boundary, but finding one with all of them on the boundary seems to be impossible.

Figure 3 - This is the BDC of the gadget of Figure 2, but it can not be embedded circular planar according to all nodes 8,9,3 and 4.

You can vary the number of nodes, the input/output nodes and the prime number $p$, nothing will help.

A good explanation is only available for the case $p = 2$. In this case it is provable that you can not even find a matrix $M$ with such a signature, because of the Desnanot-Jacobi identity (see this blog post). The Desanont-Jacobi identity is a determinant identity, which can be applied here because modulo $2$ it is $\mathsf{perm}(M) = \mathsf{det}(M)$.

There are only few things known about the relationship between planar graphs and properties of their adjacency matrix. How can then even the minors of the adjacency matrix influence the planarity of the graphs bipartite double cover in such a weird way? How does the weird property of having a signature $$(r_1,r_2,r_3,r_4,r_5,r_6) = (0,0,\neq 0,\neq 0,0,0) \pmod{p}$$ force at least one of the target nodes not to be on the boundary?


[1] Valiant, Leslie "Holographic Algorithms (Extended Abstract)". FOCS 2004. Rome, Italy: IEEE Computer Society. pp. 306–315
[2] Valiant, Leslie (2006). "Accidental Algorthims". Foundations of Computer Science, IEEE Annual Symposium on. IEEE Computer Society. pp. 509–517.