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?

alwayspositive (and fairly large). $\endgroup$ – Emil Jeřábek Mar 25 '15 at 11:00