1
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\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.