1
$\begingroup$

I found the proof of this theorem from https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf. Here is the screenshot of the construction of probabilistic Turing machine RP. (https://i.stack.imgur.com/76pyK.png)

The idea of proof is to show that if 3SAT $\in$ BPP, then 3SAT $\in$ RP. I understand the construction of the probabilistic Turing machine for RP, denoted by N. I know If $x \notin 3SAT$, then N must reject x. However, I am confused about the proof of the case where $x \in 3SAT$ (i.e. If $x \in 3SAT$, then P(N accepts x) $\ge$ $\frac{1}{2}$.). Can anyone give me some proof or comments of this case? Thank you!

$\endgroup$
1
  • $\begingroup$ If you don't understand that source, you might start by looking for another source. If you still don't understand, try to ask a more specific question about that step. It sounds like you're asking us to repeat a proof that is already widely available, and if you didn't understand it the first time you read it, I'm worried you won't understand if we try to write it, either. You might do better to explain what you do understand about that proof and ask a specific question about the first step in the proof that you don't understand. $\endgroup$
    – D.W.
    Nov 23, 2023 at 0:05

1 Answer 1

1
$\begingroup$

The idea is to use the self-reducibility of SAT to construct a search-to-decision reduction.

Suppose that we have in our disposal an oracle that solves SAT, and we wish to use it to find a satisfying assignment to a given satisfiable CNF on variables $x_1,\dots,x_n$. We use the following algorithm:

  • Substitute $x_1 = \mathsf{True}$, and check whether the CNF is still satisfiable. If so, set $x_1 = \mathsf{True}$, and otherwise, set $x_1 = \mathsf{False}$. In both cases, substitute the value of $x_1$ into the CNF.
  • Uncover the values of $x_2,\dots,x_n$ in an identical fashion.

This algorithm makes $n$ calls to the SAT oracle, and finds one of the satisfying assignments (indeed, the smallest one, under the correct order).

In your problem, you are not given an oracle to SAT, but rather a BPP algorithm. Nevertheless, you can use the same reduction. You can tune the BPP algorithm so that the error probability is at most $1/2n$ (you do this by running the given algorithm $O(\log n)$ times and taking a majority vote). You assume that the input CNF is satisfiable, and under this assumption, run the algorithm above to obtain a purported satisfying assignment. If the claimed satisfying assignment satisfies the CNF, then the CNF is obviously satisfiable, and otherwise, you declare it to be unsatisfiable.

Why does this work? You only answer "satisfiable" if the CNF is indeed satisfiable. Conversely, if the CNF is satisfiable, then the probability that any of the "oracle" calls in the algorithm fails is (in total) at most $n/2n = 1/2$, and so with probability at least $1/2$, the algorithm will find a satisfying assignment, and so will answer "satisfiable".

$\endgroup$
3
  • $\begingroup$ Thank you so much for your answer, but I am still a little bit confused about why the error probability for BPP algorithm is at most 1/2n, could you please explain how to calculate the error probability for tuned BPP algorithm specifically? Thank you in advance! $\endgroup$
    – ltl
    Nov 24, 2023 at 1:06
  • $\begingroup$ @ltl Running a BPP machine once gives you the $1/2-\epsilon$ chance of a wrong answer. That's a property of BPP from the definition. That's what separates it from PP. The rest of reasoning is in the parentheses in the answer. $\endgroup$
    – rus9384
    Nov 24, 2023 at 11:53
  • $\begingroup$ Amplifying the success probability of a BPP algorithm is standard material. You can find it in lecture notes and even on this site. $\endgroup$ Nov 26, 2023 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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