0
$\begingroup$

This Lecture summarizes some well known facts about $\#P$ completeness of permanent.

Given a CNF formula $\phi$ on $n$ variables, they construct matrix $A$ such that:

$$perm(A)=4^{3m} \#SAT(\phi)$$

This gives easy upper bound on $perm(A)$.

$\phi$ is unsatisfiable iff $perm(A)=0$, so the decision problem "Is the permanent zero (ZP)" is NP-complete.

The special case "Is the permanent of (0,1) matrix zero? (ZP01)" is polynomial.

The permanent of (0,1) matrix counts the number of vertex disjoint cycle covers of the digraph defined by this adjacency matrix, so the permanent is zero iff if the digraph doesn't have vertex disjoint cycle covers, which is polynomial.

Then on p.5 they give reduction:

Thus, for an integer matrix $A$, there exists an (0, 1)-matrix $B$, such that, $perm(B) = perm(A)\pmod{Q}$.

Soon after, remarks stops a naive attack of ZP01.

$perm(B)=0$ doesn't imply $perm(A)=0$, it implies $perm(A)=QN$ for integer $N$.

Choose $Q$ larger than the upper bound for $perm(A)$ and check if $perm(B)=0$. If this doesn't hold (cycle cover exists), then $perm(A) \ne 0$ so $\phi$ is satisfiable.

If it holds, $perm(A)=QN$ for integer $N$.

Since $Q$ is larger than the upper bound, this means $N=0$ and $perm(A)=0$, so $\phi$ is unsatisfiable.

Everything is polynomial.

What is wrong with this?

$\endgroup$
  • $\begingroup$ my understanding is that there is no good formula for permanent... $\endgroup$ – Dima Pasechnik Mar 25 '15 at 10:03
  • $\begingroup$ @DimaPasechnik I am using digraph algorithms for ZP01 and have seen the reduction to (0,1) in other papers. $\endgroup$ – joro Mar 25 '15 at 10:04
  • $\begingroup$ I have a deja vu. Didn't you ask this already some time ago? The answer is still the same: $\mathrm{perm}(A)=0$ doesn't imply $\mathrm{perm}(B)=0$. In fact, the way the reduction works, the permanent of $B$ is always positive (and fairly large). $\endgroup$ – Emil Jeřábek Mar 25 '15 at 11:00
  • $\begingroup$ @EmilJeřábek I don't think this is deja vu :). $A$ is the main matrix and $perm(A)=X$ and $B$ is (0,1) with $perm(B)=0$. We have $0 \equiv X \pmod{Q}$. So $X=Q N$. Q is greater than the upper bound, $Q > X$. $\endgroup$ – joro Mar 25 '15 at 11:42
  • $\begingroup$ @EmilJeřábek $perm(B) \not \equiv 0 \pmod{Q}$ implies $perm(A) \ne 0$. $\endgroup$ – joro Mar 25 '15 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.