Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Ghosh et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: