Abstract:

In general, it is difficult to find structural objects with certain properties. Probability methods give out a way to solve these problems： to prove   the probability of objects with certain properties is greater than zero. In probability methods, local lemma is a key technology. In this paper, we intr   oduce the basic principles, and apply the method of local lemma to （k, s）-SAT m evaluate the lower bounds of critical functions of the （k, s）-SAT p roblem.

Key words: probability method, local lemma, （k, s）-SAT problem, critical functions