Valiant converts $SAT$ formula to a $0/1$ matrix such that $Permanent$ of the matrix is $4^m\#SAT$.

We know $Permanent$ can be approximated to $1+\epsilon$ factor with probability $1-\frac1\delta$ in time $poly(m|\epsilon|^{-1}\log\frac1\delta)$.

Why does not these two help me tell when number of witnesses to $SAT$ formula is $0$ in randomized polynomial time?

What do I miss?

  • $\begingroup$ You can determine whether a non-negative matrix has permanent zero in polynomial time, using bipartite perfect matching. So I doubt your description of Valiant’s reduction. $\endgroup$ – Yuval Filmus May 26 '19 at 18:58

As you state, Valiant shows how to construct, given a CNF $\varphi$, a polynomial size matrix whose permanent is a (known) multiple of the number of satisfying assignments of $\varphi$. Unfortunately, this matrix is not non-negative.

Given a non-negative matrix, you can determine whether its permanent is zero or not using an algorithm for bipartite perfect matching; and you can efficiently estimate its value. The same doesn't hold for general matrices.

Valiant further shows how to construct, given a CNF $\varphi$, a polynomial size 0/1 matrix, from whose permanent you can deduce the number of satisfying assignments of $\varphi$. However, the formula is not as simple as before, and in particular, neither bipartite perfect matching nor the efficient permanent estimation algorithms can determine whether $\varphi$ is satisfiable or not.

For details of a later version of this last reduction, see Section 5.1 of Ben-Dor and Halevi, Zero-One Permanent is #P-Complete, A Simpler Proof.

  • $\begingroup$ As I understand we get a $\mathbb Z$ matrix with permanent $4^{3m}\#\phi$ where $m$ is number of clauses in $n$ variable formula $\phi$ and then a $\{0,1\}$ matrix with $Perm\equiv4^{3m}\#\phi\bmod 2^{m'+1}$ at some $m'\gg m$? $\endgroup$ – 1.. May 27 '19 at 11:51
  • $\begingroup$ Right, something of this sort. $\endgroup$ – Yuval Filmus May 27 '19 at 12:58
  • $\begingroup$ I am not understanding the non-triviality in formula for second reduction. If $\#\mbox{perfect-matchings}=2^{cm}\#\phi$ can't we decide no matchings and hence no witnesses? $\endgroup$ – 1.. Dec 14 '20 at 21:48
  • $\begingroup$ The formula for the second reduction is not what you state. It is more complicated. $\endgroup$ – Yuval Filmus Dec 14 '20 at 21:50
  • 1
    $\begingroup$ You can find the 0/1 matrix in Section 5.3. Also, according to Ben-Dor and Halevi, their construction combines the work of Valiant with that of Zanko (1991). $\endgroup$ – Yuval Filmus Dec 15 '20 at 8:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.