Pólya's permanent problem (Q1773170): Difference between revisions

Pólya's permanent problem has many equivalent forms: determining when all dicycles of a digraph have odd length, determining when a real square matrix is sign-nonsingular, which has applications in economics, determining whether the determinant of a nonnegative matrix equals its permanent, determining when the permanent can be computed as the determinant after changing some signs of the original matrix entries, determining whether a bipartite graph has a Pfaffian orientation, which has applications in chemistry, and various balance conditions. The author characterizes such graphs by his main theorem, that the following conditions are equivalent for a brace: a given graph is a brace with an unbalanced \(\{ -1,1\}\) edge weighting, it is a brace which does not have a well-fitted \(K_{3,3}\) subdivision, and it lies in the family consisting of the Heawood graph \(H_{14}\), all planar braces, and all graphs generated from planar braces using 4-cycle sums. This means the problem lies in NP \(\cap\) co-NP, and the author states that a polynomial-time algorithm can be derived from his lengthy proof.