5
$\begingroup$

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.

||cite|improve this question
$\endgroup$
8
+100
$\begingroup$

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?

||cite|improve this answer
$\endgroup$
4
$\begingroup$

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?

||cite|improve this answer
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Numerator Dec 29 '12 at 20:27
  • 1
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Dec 29 '12 at 23:10
  • $\begingroup$ 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. $\endgroup$ – Numerator Dec 30 '12 at 21:09
  • 2
    $\begingroup$ Ok, I'll give you a bigger hint: you have to try lots of random assignments. $\endgroup$ – Yuval Filmus Dec 30 '12 at 23:34

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.