1
$\begingroup$

How much easier is computing the permanent of a matrix with only zeroes and ones than a matrix of only integers?

$\endgroup$
0

2 Answers 2

15
$\begingroup$

There is a polynomial-time reduction from one problem to the other, as explained on Wikipedia among other places.

$\endgroup$
1
  • $\begingroup$ Very nice. I never saw that before. $\endgroup$ Apr 5, 2013 at 18:45
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.