The backtracking survey propagation algorithm for solving random K-SAT problems.
Discrete combinatorial optimization has a central role in many scientific disciplines, however, for hard problems we lack linear time algorithms that would allow us to solve very large instances. Moreover, it is still unclear what are the key features that make a discrete combinatorial optimization problem hard to solve. Here we study random K-satisfiability problems with K=3,4, which are known to be very hard close to the SAT-UNSAT threshold, where problems stop having solutions. We show that the backtracking survey propagation algorithm, in a time practically linear in the problem size, is able to find solutions very close to the threshold, in a region unreachable by any other algorithm. All solutions found have no frozen variables, thus supporting the conjecture that only unfrozen solutions can be found in linear time, and that a problem becomes impossible to solve in linear time when all solutions contain frozen variables.
NORDITA and AlbaNova University Centre, Department of Computational Biology, KTH-Royal Institute of Technology and Stockholm University, Roslagstullsbacken 23, SE-10691 Stockholm, Sweden.
Raffaele
R
Marino
Dipartimento di Fisica, Sapienza Università di Roma and Istituto Nazionale di Fisica Nucleare, Sezione di Roma1 and CNR-Nanotec, Unità di Roma, P.le Aldo Moro 5, I-00185 Roma, Italy.
Giorgio
G
Parisi
Dipartimento di Fisica, Sapienza Università di Roma and Istituto Nazionale di Fisica Nucleare, Sezione di Roma1 and CNR-Nanotec, Unità di Roma, P.le Aldo Moro 5, I-00185 Roma, Italy.
Federico
F
Ricci-Tersenghi
Phys Rev E Stat Nonlin Soft Matter Phys. 2002 Nov;66(5 Pt 2):056126
12513575
Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Mar;77(3 Pt 1):031118
18517340
Science. 2002 Aug 2;297(5582):812-5
12089451
Science. 1994 May 27;264(5163):1297-301
17780846
Phys Rev E Stat Nonlin Soft Matter Phys. 2006 Sep;74(3 Pt 2):037702
17025790
Proc Natl Acad Sci U S A. 2007 Jun 19;104(25):10318-23
17567754
Phys Rev E Stat Nonlin Soft Matter Phys. 2007 Sep;76(3 Pt 1):031131
17930223
Phys Rev Lett. 2002 Dec 23;89(26):268701
12484862
Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Oct;78(4 Pt 1):040101
18999364