Timeline for Complexity of permanent verification
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 5, 2023 at 1:31 | vote | accept | Igor Pak | ||
| Jul 3, 2023 at 15:46 | answer | added | Ryan Williams | timeline score: 8 | |
| Jul 1, 2023 at 6:26 | comment | added | Emil Jeřábek | @Bruno Yes, as I already mentioned, the reduction up to $\{-1,0,1\}$-matrices does give a well-defined function of the number of satisfying assignments, and shows that the permanent verification problem for $\{-1,0,1\}$-matrices is $\mathrm{C_=P}$-complete. | |
| Jun 30, 2023 at 20:38 | comment | added | Bruno | @EmilJeřábek I suspected this was too easy. The problem is going from say $\{-1,0,1\}$-matrices to $\{0,1\}$-matrices, right? or do I miss something else? | |
| Jun 30, 2023 at 13:49 | comment | added | Emil Jeřábek | @Bruno No, that’s the problem. Valiant’s proof works so that $\mathrm{Per}(A_\phi)$ is only congruent to a known function of the number of satisfying assignments modulo a large known number $Q$. You do not know what multiple of $Q$ you added; there are exponentially many possibilities, and computing it is likely #P-hard on its own. Thus, this does not give you a polynomial-time computable $f$. | |
| Jun 30, 2023 at 12:58 | comment | added | Bruno | I think it is indeed NP-hard. (Hopefully I am not writing stupid things...) First, deciding whether a 3-CNF formula has $k$ satisfying assignments is NP-hard since this encompasses the standard 3-SAT. Then Valiant's proof of #P-completeness of the permanent turns a formula $φ$ into a $0,1$-matrix $A_φ$ such that $per(A_φ)$ is a (known) function $f$ of the number of satisfying assignments of $φ$. Valiant's reduction can therefore be seen as a reduction from $(φ, k)$ to $(A_φ, f(k))$, proving the NP-hardness of your problem. | |
| Jun 30, 2023 at 6:14 | history | edited | Igor Pak | CC BY-SA 4.0 |
edited title
|
| Jun 30, 2023 at 5:35 | comment | added | Emil Jeřábek | Hmm. It’s $\mathrm{C_=P}$-complete for $\{-1,0,1\}$-matrices (and for general integer matrices, of course). | |
| Jun 29, 2023 at 23:54 | history | asked | Igor Pak | CC BY-SA 4.0 |