Regular Random k-SAT: Properties of Balanced Formulas |
| |
Authors: | Yacine Boufkhad Olivier Dubois Yannet Interian Bart Selman |
| |
Affiliation: | (1) LIAFA, CNRS-Université Denis Diderot- Case 7014, 2, place Jussieu, 75251 Paris Cedex 05, France;(2) LIP6, Box 169, CNRS-Université Paris 6, 4 place Jussieu, 75252 Paris Cedex 05, France;(3) Center for Applied Mathematics, Cornell University, Ithaca, NY 14853, USA;(4) Depatiment of Computer Science, Cornell University, Ithaca, NY 14853, USA |
| |
Abstract: | We consider a model for generating random k-SAT formulas, in which each literal occurs approximately the same number of times in the formula clauses (regular random
and k-SAT). Our experimental results show that such regular random k-SAT instances are much harder than the usual uniform random k-SAT problems. This is in agreement with other results that show that more balanced instances of random combinatorial problems
are often much more difficult to solve than uniformly random instances, even at phase transition boundaries. There are almost
no formal results known for such problem distributions. The balancing constraints add a dependency between variables that
complicates a standard analysis. Regular random 3-SAT exhibits a phase transition as a function of the ratio α of clauses to variables. The transition takes place at approximately α = 3.5. We show that for α > 3.78 with high probability (w.h.p.) random regular 3-SAT formulas are unsatisfiable. Specifically, the events hold with high probability if Pr
when n → ∞. We also show that the analysis of a greedy algorithm proposed by Kaporis et al. for the uniform 3-SAT model can be adapted
for regular random 3-SAT. In particular, we show that for formulas with ratio α < 2.46, a greedy algorithm finds a satisfying assignment with positive probability. |
| |
Keywords: | satisfiability phase transition k-SAT regular Boolean formulae |
本文献已被 SpringerLink 等数据库收录! |
|