# 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 '19 at 18:58

## 1 Answer

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.

• 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$? – 1.. May 27 '19 at 11:51
• Right, something of this sort. – Yuval Filmus May 27 '19 at 12:58
• 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? – 1.. Dec 14 '20 at 21:48
• The formula for the second reduction is not what you state. It is more complicated. – Yuval Filmus Dec 14 '20 at 21:50
• 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). – Yuval Filmus Dec 15 '20 at 8:49