# Why does not valiant's reduction show NP=RP?

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?

• 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. – Yuval Filmus May 26 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.
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.
• 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$? – T.... May 27 at 11:51