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.