Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs (Q911300)

The problem of whether one can change some \(+1\) into -1 of a (0,1) matrix A so that the determinant of the resultant matrix equals the permanent of A is proved to be polynomial-time equivalent to the problem of determining whether a directed graph has an even length simple cycle. The problem of determining whether a graph has a Pfaffian orientation is proved to be polynomial-time equivalent to the problem whether a given orientation of a graph is Pfaffian. Both problems are actually in Co-NP. Let A be a an \(n\times n\) integer matrix. The problem \(``\det (A)=perm(A)?''\) is NP-hard. It is polynomial-time equivalent to the problem of even cycles if A is a (0,1) matrix.