randomized algorithm for checking the satisfiability of s-formulas, that outputs the correct answer with probability at least $\frac{2}{3}$

Question

I'm trying to practice myself with random algorithms.

Lets call a CNF formula over n variables s-formula if it is either unsatisable or it has at least $\frac{2^n}{n^{10}}$ satisfying assignments.

I would like your help with show a randomized algorithm for checking the satisfiability of s-formulas, that outputs the correct answer with probability at least $\frac{2}{3}$.

I'm not really sure how to prove it. First thing that comes to my head is this thing- let's accept with probability $\frac{2}{3}$ every input. Then if the input in the language, it was accepted whether in the initial toss($\frac{2}{3}$) or it was not and then the probability to accept it is $\frac{1}{3}\cdot proability -to-accept$ which is bigger than $\frac{2}{3}$. Is this the way to do that or should I use somehow Chernoff inequality which I'm not sure how.

Answer 1

Basic idea: Pick a random assignment and check it. Then, repeat it many times. Even if one of the assignments satisfies the formula you answer "YES" (otherwise, you answer "NO")

We know that the input formula is "simple": in plain words it means that either it is not-satisfiable or it has "many" satisfying assignments. If it is not satisfiable - no matter what assignment(s) you choose, it will never satisfy the formula. Therefore, the above algorithm always answers correctly for such inputs, and from this point and on we consider only satisfiable inputs.

If the input is satisfiable, what is the probability that a random assignment satisfies it?

Let $\varphi$ be a CNF over $n$ variables with more than 2ドル^n/n^{10}$ satisfying assignments, then $$ \Pr_{x\sim U}[ \varphi(x)=T] \ge \frac{2^n/n^{10}}{2^n}$$

Now we repeat it $k$ times (you'll have to pick $k$ carefully. Let's do it later). Each time we pick a random $x$. Let $E_i$ be the event that in the $i$-th instance $\varphi$ is satisfied. What is the probability that we find out at least one satisfying assignment after $k$ tries?

It is $\Pr[\bigcup_{i=1}^k E_i]$. We know that $\Pr[E_i] \ge 1/n^{10},ドル and you can use standard linearity (of independent events) to work it out.

Final step - find the (minimal) $k$ that makes $\Pr[\cup_k E_i] \ge 2/3$ as required.

Bonus question: how low can you make $k$ (and make your algorithm more efficient) if you analyze the above using Chernoff's inequality?

Answer 2

Your suggestion doesn't work. When the formula is unsatisfiable, your algorithm outputs the correct answer with probability 1ドル/3$ only.

Hint: If a formula has 2ドル^n/n^{10}$ satisfying assignments, what's the probability that a random assignment is satisfying?

• Numerator: It is $\frac{1}{n^10},ドル how should I continue? I need to show that the problem is in $BPP ( \frac{1}{3}, \frac {2}{3}),ドル right? should I need to show $BPP( \frac{1}{3}, \frac{2}{3})=something-else$? Thank you!
• Yuval Filmus: Suppose you suspect that the formula has 2ドル^n/n^{10}$ satisfying assignments. How can you verify this fact, say by finding a satisfying assignment?
• Numerator: Maybe check that there are 2ドル^n-\frac{2^n}{n^{10}}$ which not satisfying the formula? I'm not sure where you are going.
• Yuval Filmus: Ok, I'll give you a bigger hint: you have to try lots of random assignments.