0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This is not a research-level question, as pointed out below the answer can be found on the Wikipedia article. Voting to close as off-topic. $\endgroup$ – Kaveh Jun 14 '13 at 2:34
  • $\begingroup$ @Kaveh Direct or migrate to CS maybe? So they don't come back. $\endgroup$ – Tobi Alafin Dec 27 '16 at 8:15
14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very nice. I never saw that before. $\endgroup$ – Craig Feinstein Apr 5 '13 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, privacy policy and cookie policy

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