Biased random satisfiability problems: From easy to hard instances

Abstract

In this paper we study biased random K-SAT problems in which each logical variable is negated with probability $p$. This generalization provides us a crossover from easy to hard problems and would help us in a better understanding of the typical complexity of random K-SAT problems. The exact solution of 1-SAT case is given. The critical point of K-SAT problems and results of replica method are derived in the replica symmetry framework. It is found that in this approximation ${\alpha }_c\propto p^{-(K-1)}$ for $p\to 0$. Solving numerically the survey propagation equations for K=3 we find that for $p<p^{\ast }\sim 0.17$ there is no replica symmetry breaking and still the SAT-UNSAT transition is discontinuous.

17 pages, 8 figures