Timeline for What is wrong with the argument that zero permanent is polynomial?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 10, 2023 at 4:06 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 10, 2023 at 3:53 | answer | added | Alejandro Quinche | timeline score: -1 | |
| Mar 25, 2015 at 13:01 | review | Close votes | |||
| Mar 25, 2015 at 14:56 | |||||
| Mar 25, 2015 at 12:53 | comment | added | Emil Jeřábek | Btw, your previous question is here: mathoverflow.net/q/172909 . (The question is not the same, but the underlying confusion is.) | |
| Mar 25, 2015 at 12:32 | comment | added | joro | @EmilJeřábek you might be right, thanks :) btw, for Q=2^k, you can compute the permanent modulo Q in O(n^4k), but this is another story. | |
| Mar 25, 2015 at 11:55 | comment | added | Emil Jeřábek | 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. | |
| Mar 25, 2015 at 11:49 | comment | added | joro | @EmilJeřábek $perm(B) \not \equiv 0 \pmod{Q}$ implies $perm(A) \ne 0$. | |
| Mar 25, 2015 at 11:42 | comment | added | joro | @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$. | |
| Mar 25, 2015 at 11:00 | comment | added | Emil Jeřábek | 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). | |
| Mar 25, 2015 at 10:04 | comment | added | joro | @DimaPasechnik I am using digraph algorithms for ZP01 and have seen the reduction to (0,1) in other papers. | |
| Mar 25, 2015 at 10:03 | comment | added | Dima Pasechnik | my understanding is that there is no good formula for permanent... | |
| Mar 25, 2015 at 9:59 | history | asked | joro | CC BY-SA 3.0 |