The Permanent and planar graphs

Computational Complexity is a really fascinating area of research. One particular surprising fact that i learned years ago is the discrepancy between the computational effort to compute the determinant of a matrix and the permanent of a matrix. The determinant is defined as:
\begin{equation}
\text{det}(\text{A}) = \sum_{\sigma \in S_n}\text{sign}(\sigma)\prod^n_{i=1}a_{i,\sigma_i}
\end{equation} and the permanent is
\begin{equation}
\text{perm}(\text{A}) = \sum_{\sigma \in S_n}\prod^n_{i=1}a_{i,\sigma_i}
\end{equation} The difference in notation is minimal. The determinant considers the sign of the permutations $\sigma$ whereof the permanent does not. This little difference is responsible for the huge gap between the necessary resources that are needed in order to compute the actual value of these functions. The determinant can be evaluated in time that is polynomial in the dimension $n$, whereof the permanent is only computable in time that is exponential in $n$, e.g., using the $\mathcal{O}(n2^n)$ algorithm of Ryser. In the year 1979 Leslie Valiant [1,2] showed that the permanent is even #P-complete and he shows the same for any computation of $\text{perm}(\text{A}) \mod{p}$ for $p > 2$. To proof this, Valiant created a graph that encodes a boolean formula $f$. Due to his clever construction, the permanent of the graph's adjacency matrix is equal to the number of satisfying solution of the boolean formula $f$. It is a beutiful result and shows clearly that the computation of the permanent can probably not be done in an efficient way, i.e., polynomial in the matrix dimension. Note that if someone could compute the number of satisfying solutions of a formula $f$, such an algorithm can also be used to:

1. Decide if a given formula $f$ satisfiable, i.e. to solve the $\text{SAT}$ problem
2. If $f$ is satisfiable, to give a satisfying assignment of its variables. (Can be used to factorize integers)

# A question #

I asked the following question in a well known forum for this kind of research, but got no satisfying answers. Here is what i asked:

The two authors Ben-Dor/Halevi [3] gave another proof of the fact that the permanent is #P-complete. Additionally, in their paper they show the reduction chain $$\text{IntPerm} \rightarrow \text{NoNegPerm}\rightarrow \text{2PowersPerm} \rightarrow \text{0/1-Perm}$$ while the permanent value is preserved along the chain. That means, they converted an integer matrix with a certain permanent value to a matrix that only has 0/1-values (but is larger) and has the same permanent value.

However, it is well known that the permanent of a 0/1-matrix $\text{A}$ is equal to the number of perfect matchings in the bipartite double cover $G$, i.e., the graph from the matrix
\begin{equation}
\begin{bmatrix}
0 & A \\
A^t & 0
\end{bmatrix}
\end{equation} And this number of perfect matching can be computed efficiently, i.e., polynomial in the dimension, if $G$ is planar. The algorithm that does this, is Kastelyens algorithm or the improved FKT version.

Following the complete argumentation line, the consequence is:

1. Pick a boolean formula $f$.
2. Construct the graph as explained by Valiant such that the permanent of its adjacency matrix is equal to the number of satisfying solutions of $f$.
3. Convert the graph according to the description of Ben-Dor and Halevi such that its adjacency matrix contains only 0/1 values but has the same permanent value.
4. Construct the bipartite double cover of that new graph
5. Test if that bipartite double cover is planar: If yes, compute the number of perfect matchings with the FKT algorithm, which is equal to the permanent of the original graph. If no, stop or change the formula $f$.

Since all those steps can be done efficiently, there must be a showstopper somewhere. The showstopper is that the bipartite double cover will be almost always non-planar. Hence the FKT algorithm fails. Furthermore, Step 3 increases the number of nodes of the graph enormous, but which can be removed when one steps to finite fields.

But the interesting question which arises is:

Is there a class of boolean formulas which lead more often to planar graphs than others?

In my paper, i uploaded on arxiv several month ago, i deal with this topic. The outcome o0f the study is, that a large portion of the problem can be reduced to the topic of circular planar (sub-)graph that fulfil the Desnanot-Jacobi identity over finite fields $\mathbb{F}_p$ and $p > 3$ and that probably do not exists.

One particular and even cryptographic related fact i stumbled across during working on this, is the following: One could factorize integers in polynomial time if he can find a matrix with the following properties:

Let $M$ be a $n\times n$ matrix with 0/1 entries and $n > 3$ with the following properties: 

• $\text{det}(M)$ is even

• For any non-empty subsets $I,J \subseteq \{1,2,3\}$ with $|I|=|J|$, the determinant of the submatrix $M^I_J$ is odd if and only if $I=J$

Here $M^I_J$ denotes the submatrix of $M$ created by removing the rows with indices in $I$ and the columns with indices in $J$.

Sadly, Peter Shor (yes, the Peter that invented that quantum factoring algorithm) answered my question regarding such a matrix in a negative way and showed that the Desnanot-Jacobi identity forbids that such a matrix exits.

Theorem [Desnanot-Jacobi identity] Given the matrix $M = m_{i,j}$ with $1 \leq i,j \leq n$ then the following equation is always true \begin{equation} \text{det}(M)\text{det}(M^{i,j}_{i,j}) = \text{det}(M^i_i)\text{det}(M^j_j) - \text{det}(M^i_j)\text{det}(M^j_i) \end{equation}

For example, we could set $I = 1$ and $J = 2$ and hence we get
\begin{equation}\text{(}1\text{)}\;\;\;
\text{det}(M)\text{det}(M^{1,2}_{1,2}) = \text{det}(M^1_1)\text{det}(M^2_2) - \text{det}(M^1_2)\text{det}(M^2_1)
\end{equation} according to the Desnanot-Jacobi identity. But the requirement was that $\text{det}(M)$ is even, hence the LHS of Eq. 1 is $0$ modulo $2$. The second requirement was that $\text{det}(M^1_2)$ and $\text{det}(M^2_1)$ have to be odd and $\text{det}(M^1_1)$ and $\text{det}(M^2_2)$ have to be even. That makes the RHS of Eq. 1 to $1$ modulo $2$, so such a matrix can not exists.


[1] Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189–201, 1979.
[2] Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal of Computation, 8(3):410–421, 1979.
[3] Amir Ben-Dor and Shai Halevi. Zero-one permanent is #P-complete, a simpler proof. In 2nd Israel Symposium on Theory of Computing Systems, pages 108–117, 1993. Natanya, Israel.