gotchaMinor
Why does not valiant's reduction show NP=RP?
Viewed 0 times
showwhyvaliantreductiondoesnot
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#109894, answer score: 2
Revisions (0)
No revisions yet.