Biased initialization in random walk algorithms for k -SAT: a generalization of Schöning's method
Subhas Kumar Ghosh, Vijay Monic Vittamsetti · International Journal of Parallel Emergent and Distributed Systems · 2025
In this paper, we improve Schöning's time-bounded random walk algorithm for k-SAT by using a biased coin to select the initial assignment. The algorithm we present extends the idea of Hofmeister, Schöning, Schuler, and Watanabe (Theor. Comp. Sys. 2007). Their method of selecting the initial assignment based on the structural properties of the input formula was designed for 3-SAT. We extend this approach to general k-SAT formulas. We compare our algorithm with that of Paturi et al. (FOCS 1997) for k-SAT, and show that our algorithm offers improvement for smaller values of k.