4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – pseudoturing Feb 3 at 13:39
  • $\begingroup$ I suggest spending more time with the answer, trying to decipher it. $\endgroup$ – Yuval Filmus Feb 3 at 13:45
  • $\begingroup$ studying and trying to decipher it. thank you $\endgroup$ – pseudoturing Feb 6 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.