Finite-size scaling in random $K$-satisfiability problems

We provide a comprehensive view of various phase transitions in random $K$-satisfiability problems solved by stochastic-local-search algorithms. In particular, we focus on the finite-size scaling (FSS) exponent, which is mathematically important and practically useful in analyzing finite systems. Using the FSS theory of nonequilibrium absorbing phase transitions, we show that the density of unsatisfied clauses clearly indicates the transition from the solvable (absorbing) phase to the unsolvable (active) phase as varying the noise parameter and the density of constraints. Based on the solution clustering (percolation-type) argument, we conjecture two possible values of the FSS exponent, which are confirmed reasonably well in numerical simulations for $2\le K\le 3$.

Figure 1

(Color online) FSS for 2-SAT by ASAT with $p=1/2$, where logarithmic corrections to scalings are found as (a) $⟨{\rho }_u\left(N,t\right)⟩N^{\theta }=f\left(t/\left[N^{\overline{z}}/\text{ln}\left(N\right)\right]\right)$ and (b) ${\tau }_{\text{H}}\left(\alpha ,N\right)/\left[N^{\overline{z}}/\text{ln}\left(N\right)\right]=h\left(\left|ϵ\right|N^{1/\overline{\nu }}\right)$ with $ϵ=\left(\alpha -{\alpha }_c\right)/{\alpha }_c$. For the convenience, the same symbols and lines are taken to the same system sizes in Figs. 2, 3.

Figure 2

(Color online) FSS for 3-SAT by the limiting case of ASAT $\left(p=1\right)$, RandomWalkSAT, with logarithmic corrections to scalings as (a) $⟨{\rho }_u\left(N,t\right)⟩\left[N^{\theta }/\text{ln}\left(N\right)\right]=f\left(t/\left[N^{\overline{z}}\text{ln}\left(N\right)\right]\right)$ and (b) ${\tau }_{\text{H}}\left(\alpha ,N\right)/\left[N^{\overline{z}}\text{ln}\left(N\right)\right]=h\left(\left|ϵ\right|N^{1/\overline{\nu }}\right)$. The same symbols and lines are taken to the same system sizes as in Fig. 1.

Figure 3

(Color online) FSS for 3-SAT by the optimized ASAT $\left(p=p_{\text{opt}}\simeq 0.21\right)$ with logarithmic corrections to scalings as (a) $⟨{\rho }_u\left(N,t\right)⟩N^{\theta }=f\left(t/\left[N^{\overline{z}}/\text{ln}\left(N\right)\right]\right)$ and (b) ${\tau }_{\text{H}}\left(\alpha ,N\right)/\left[N^{\overline{z}}/\text{ln}\left(N\right)\right]=h\left(\left|ϵ\right|N^{1/\overline{\nu }}\right)$. The same symbols and lines are taken to the same system sizes as in Fig. 1.