2
$\begingroup$

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?

$\endgroup$
  • $\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 at 18:58
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – Turbo May 27 at 11:51
  • $\begingroup$ Right, something of this sort. $\endgroup$ – Yuval Filmus May 27 at 12:58

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.