The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers How much easier is computing the permanent of a matrix with only zeroes and ones than a matrix of only integers?
There is a polynomial-time reduction from one problem to the other, as explained on Wikipedia among other places.