4
$\begingroup$

Going through the literature, it seems that what it comes down to is that if one could efficiently approximate permanents of matrices with negative entries, then that would imply an efficient algorithm for calculating permanents of 0/1 matrices exactly. On the other hand, Valiant provided a polynomial time reduction from the permanent of an arbitrary matrix with integer entries to the permanent of a 0/1 matrix. Why could one not make use of this reduction, followed by an application of the JSV algorithm (which can efficiently approximate the permanents of matrices with nonnegative entries but cannot handle matrices with negative entries) to efficiently approximate the permanents of arbitrary integer matrices?

$\endgroup$
10
$\begingroup$

The answer to the title question is: it's difficult to simulate a Markov chain with negative transition probabilies.

Valiant's reduction uses the Chinese remainder theorem, which requires an exact number, not just an approximation. The JSV algorithm cannot tell you what the permanent of a matrix is modulo 3, for example.

The type of reductions you'd need to reduce to JSV were named "approximation preserving reductions" by Dyer at al. An approximation-preserving reduction from a problem X to a problem Y is a way of turning an FPRAS for Y into an FPRAS for X (in a way that relativises). A simpler case of the same pattern is #DNF and #SAT:

  • There is an approximation algorithm (an FPRAS) for counting solutions of a formula in disjunctive normal form.
  • It is NP hard to approximate the number of solutions of a formula in conjunctive normal form to within a multiplicative constant (because it is NP hard to determine whether there is any satisfying assignment at all).
  • There is a reduction from #SAT to #DNF: given a CNF formula $\phi$ on $n$ variables, replace all the conjunctions by disjunctions and vice versa. If the resulting formula has $x$ solutions, then $\phi$ has $2^n-x$ solutions.

There is no contradiction, because the reduction described above is not approximation-preserving. Another common non-approximation-preserving reduction for counting problems is polynomial interpolation.

$\endgroup$
  • $\begingroup$ I see. The problem of calculating the permanent exactly is just as hard if the matrix has arbitrary integer entries as if the matrix is 0/1. However, allowing for approximation separates the problem into an easy case (nonnegative entries) and a hard case (arbitrary integer entries). I suppose I'm still confused on the point that the reduction is not approximation-preserving. By construction, the absolute value of the permanent cannot be greater than what you mod out by, so there are only two possible cases. What if I were to instead ask for only the absolute value of the permanent? $\endgroup$ – Adrian Nov 28 '13 at 1:52
  • $\begingroup$ @Adrian: in the reduction given in Proposition 3.4 in "The complexity of computing the permanent", the primes "$p_i$" are generally less than the absolute value of the permanent, for which only the upper bound "$\mu^n n!$" is known. $\endgroup$ – Colin McQuillan Nov 28 '13 at 11:15

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.