How much easier is computing the permanent of a matrix with only zeroes and ones than a matrix of only integers?
The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
There is a polynomial-time reduction from one problem to the other, as explained on Wikipedia among other places.
-
$\begingroup$ Very nice. I never saw that before. $\endgroup$ Commented Apr 5, 2013 at 18:45
$\begingroup$
$\endgroup$
The permanent of a 01-matrix is equal to the number of vertex cycle covers of an unweighted directed graph. Its computation is #P-complete.
