Permanents, Pfaffian orientations, and even directed circuits (extended abstract)
Permanents, Pfaffian orientations, and even directed circuits (extended abstract)
复制标题
DOI：
10.1145/258533.258625
复制
发表时间：
1997-05
期刊：
影响因子：
--
通讯作者：
W. McCuaig;N. Robertson;P. Seymour;R. Thomas
中科院分区：
文献类型：
--
作者：
W. McCuaig;N. Robertson;P. Seymour;R. Thomas
计算复杂性的以下问题仍然没有得到精确的理解：计算矩阵的积和行列式的复杂性的显著差异，尽管它们看起来相似的公式，检查有向图是否包含偶数长度的循环的复杂性，以及使用Pfweian方向计算图中完美匹配的数量的复杂性。通过多项式时间等价，我们显示这些问题之间的相互关系。
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.