-1
$\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?

Improve this question
$\endgroup$
8
  • $\begingroup$ my understanding is that there is no good formula for permanent... $\endgroup$
    – Dima Pasechnik
    Commented Mar 25, 2015 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
    Commented Mar 25, 2015 at 10:04
  • 1
    $\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
    Commented Mar 25, 2015 at 11:00
  • 2
    $\begingroup$ You cannot test whether perm(B) is nonzero modulo Q. You can only test whether it is nonzero, and that does not tell you anything about A. $\endgroup$
    – Emil Jeřábek
    Commented Mar 25, 2015 at 11:55
  • 1
    $\begingroup$ Btw, your previous question is here: mathoverflow.net/q/172909 . (The question is not the same, but the underlying confusion is.) $\endgroup$
    – Emil Jeřábek
    Commented Mar 25, 2015 at 12:53

1 Answer 1

Reset to default
-1
$\begingroup$

I understand this question is not research level but I feel Emil never left a satisfying answer that convinced me that that joro argument was wrong.

Let's see why there are unsatisfiable assignments that we could not detect with this approach, suppose we get from our query to the perfect matching that the permanent is non zero, to calculate the correct value of $Perm(A)$ (what actually reflects satisfiability) we need the mod, so if $Perm(B)$ is $NQ$ we wouldn't detect it, your argument that $N$ has to be zero forgets that the bound is for $Perm(A)$ not $Perm(B)$, and $B$ is a different matrix with much bigger numbers.

I have given some thought to this an it seems if we actually get that the permanent is zero this does reflect that the formula is really unsatisfiable, what Emil suggested would be that this case would be almost non existent because a perfect matching is almost ensured, however I find interesting how many unsatisfiable assignments will actually be multiples of $Q$ as this can tell us how much we could trust the non zero responses, maybe it's a fair amount of them even around half of them, making this test almost as usable as trowing a coin to determine satisfiability. A proof of this or similar ideas seems interesting but probably has already been studied for approximation SAT algorithms but I guess I will have to dig more into this to confirm it for you.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ I think the point is: you can check if $\operatorname{perm}(B) \neq 0$. If that happens, then OP wanted to deduce that therefore $\operatorname{perm}(B) \not\equiv 0 \pmod{Q}$, hence $\operatorname{perm}(A) \not\equiv 0 \pmod{Q}$, hence $\operatorname{perm}(A) \neq 0$. But the very first deduction is wrong: $x \neq 0$ doesn't imply $x \not\equiv 0 \pmod{Q}$. In conclusion, $\operatorname{perm}(B) \neq 0$ ("easy" to test) doesn't imply $\operatorname{perm}(A) \neq 0$ (what we want to test) (Emil stated the contrapositive, $\operatorname{perm}(A) = 0$ doesn't imply $\operatorname{perm}(B) = 0$.) $\endgroup$
    – Zach Teitler
    Commented Apr 10, 2023 at 4:59
  • $\begingroup$ I see, obviously this breaks the $NP=P$ argument but if we do get $perm(B)=0$ we would have the implication that $perm(A)=0$ right? I also find funny that for "false positives" we would precisely fall in multiples of $Q$ but maybe there's a simple divisibility argument to be made to make this obvious. $\endgroup$
    – Alejandro Quinche
    Commented Apr 10, 2023 at 12:37
  • $\begingroup$ Just to add to your comment user knew that $x \not = 0$ doesn't imply $ x \not = 0 \mod Q$ however he thought that $|x|$ was bounded strictly by $Q$ and in that case we have that implication $\endgroup$
    – Alejandro Quinche
    Commented Apr 10, 2023 at 14:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .