Problem Detail: 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.
Asked By : Numerator
Answered By : Ran G.
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_{xsim 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?
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7641 Ask a Question Download Related Notes/Documents
