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

An implementation of the FKT-algorithm

This post is dedicated to give you an implementation (in SAGE) of the FKT-algorithm. I coded this while spending some time on the ideas i explained in this blog post. I searched several hours to find an existing implementation without success. Since it took me a while to code this on my own, i think it is worth to present it, therewith other can use it in their own work. It works well, but if you find an error, please leave a note.

The FKT-algorithm can be used to count the number of perfect matchings in a planar graph. And a graph is planar if and only if it does not have K$_5$ or K$_{3,3}$ as a minor.

A paper that will be presented at the CCC conference this year is called:

Counting the Number of Perfect Matchings in $K_5$-free Graphs [in polynomial time] Simon Straub (Ulm University), Thomas Thierauf (Aalen University), Fabian Wagner (Ulm University)

I did not manage to read it yet, but i am curious to see, how they circumvent the K$_{3,3}$ minor problem.

########################################################################
# AUTHOR: Dr. Christian Schridde
# E-MAIL: christianschridde [at] googlemail [dot] com
#
# DESCRIPTION: Implementation of the FKT-algorithm
#
# INPUT:  Adjacency matrix A of a undirected loop-free planar graph G
# OUTPUT: Skew matrix M, such that PerfMatch(G) = Sqrt(Determinat(M))
########################################################################