Can we show that #3CNF is in FPTAS

Question

If we have a deterministic algorithm $A$ such that $\#3CNF \in APX$, how can we show that there is a fully polynomial deterministic approximation scheme for $\#3CNF$? How can we show that $\#3CNF \in FPTAS$?

Answer 1

Given a CNF $\varphi$, you can create a CNF $\varphi^{(2)}$ such that $N(\varphi^{(2)}) = N(\varphi)^2$, where $N(\varphi)$ is the number of assignments satisfying $\varphi$. If you apply a #SAT approximation algorithm to $\varphi^{(2)}$, then you get an approximation of $N(\varphi)$ which is better than what you would get if you applied the algorithm directly on $\varphi$. To get an even better approximation, create a CNF $\varphi^{(k)}$ such that $N(\varphi^{(k)}) = N(\varphi)^k$.

In your case you have the additional complicated that everything is a 3CNF, but I suggest starting without this restriction.