Biased random satisfiability problems: From easy to hard instances

In this paper we study biased random $K$-satisfiability ($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^{*}\sim 0.17$ there is no replica symmetry breaking and still the SAT-UNSAT transition is discontinuous.

Figure 1

Factor graph of the formula given in Eq. (1).

Figure 2

Ground state energy of the 1-SAT problem from top to bottom for $p=1∕2$, $p=1∕4$, and $p=1∕6$.

Figure 3

Ground state entropy of the 1-SAT problem from top to bottom for $p=1∕2$, $p=1∕4$, and $p=1∕6$.

Figure 4

$S_0$ experiences a cavity field determined from the fields experienced by the other neighbors of function nodes 1,2,3.

Figure 5

${\alpha }_c$ versus $p$ for $K=3$ and in the replica symmetric approximation. The line shows a power law of exponent 2.

Figure 6

The survey warning ${\eta }_{a\to i}$ is determined by the set of surveys ${\eta }_{b\to j}$.

Figure 7

From top to bottom: the replica symmetry predictions for ${\alpha }_c$ (RS), survey propagation predictions of ${\alpha }_c$ (SP) and ${\alpha }_d$ (SP) for $K=3$ and $N=\mathrm{10\hspace{0.17em}000}$. The numerical results have been obtained for one realization with the convergence limit equal to 0.001.

Figure 8

Maximum complexity of the 3-SAT in terms of $p$. The parameters are the same as Fig. 7.