Pfaffian orientations, 0–1 permanents, and even cycles in directed graphs
Vijay V. Vazirani, Mihalis Yannakakis · Discrete Applied Mathematics · 1989
The following issues in computational complexity remain imprecisely understood: The striking difference in the complexities of computing the permanent and determinant of a matrix despite their similar looking formulae, the complexity of checking if a directed graph contains an even length cycle, and the complexity of computing the number of perfect matchings in a graph using Pfaffian orientations. Via polynomial time equivalences, we show inter-relationships among these issues.