# why does $A≤_p \#SAT$ if $A \in BPP$

hello and thank you for helping me understand the following:

I really don't understand this, why if language $$A \in BPP$$ then $$A≤_P\#SAT$$?

language A is in BPP class, if for a probabilistic turing machine M, M outputs 1 for all $$x \in A$$ in a probability $$\geq 2/3$$, and for all $$x \not \in A$$ M outputs 1 in a probability of $$\leq 1/3$$ and of course M must run in a polynomial time on all inputs.

so if $$A \in BPP$$, why does it mean that $$A≤_P\#SAT$$? if M is reduced to boolean F, it means that we'll get output of 1 in a probability of $$\geq 2/3$$ for every $$x \in A$$? why?

can someone please show me algorithmically or mathmatically why if language $$A \in BPP$$ then $$A≤_P\#SAT$$? quite lost

thank you, would appreciate if you could explain along.

Using the proof of the Cook–Levin theorem, for every input $$x$$ you can construct in polynomial time a SAT instance $$\phi(r,z)$$ which encodes "$$M$$ accepts when run on input $$x$$ and randomness $$r$$". Here $$r$$ is a vector of $$m = \mathit{poly}(n)$$ bits, representing the random bits of $$M$$, and $$z$$ is an auxiliary vector, with the following property: in any accepting run of $$M$$, there is exactly one setting of $$z$$ which satisfies $$\phi$$.
By definition, if $$x \in L$$ then $$\phi$$ has at least $$(2/3)2^m$$ satisfying assignments, and if $$x \notin L$$ then $$\phi$$ has at most $$(1/3)2^m$$ satisfying assignments. You can distinguish between the two cases using a $$\mathsf{\#SAT}$$ oracle.
• can you please explain and elaborate? why does $(2/3) 2^m$? i don't understand the $2^m$. can you show it like a proof please so it will be easier to understand the steps and what's behind them? thank you very much – pseudoturing Feb 3 '20 at 13:39