The backtracking survey propagation algorithm for solving random K-SAT problems

Raffaele Marino, Giorgio Parisi () and Federico Ricci-Tersenghi
Additional contact information
Raffaele Marino: NORDITA and AlbaNova University Centre, KTH-Royal Institute of Technology and Stockholm University
Giorgio Parisi: Sapienza Università di Roma and Istituto Nazionale di Fisica Nucleare, Sezione di Roma1 and CNR-Nanotec
Federico Ricci-Tersenghi: Sapienza Università di Roma and Istituto Nazionale di Fisica Nucleare, Sezione di Roma1 and CNR-Nanotec

Nature Communications, 2016, vol. 7, issue 1, 1-8

Abstract: Abstract 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.

Date: 2016
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.nature.com/articles/ncomms12996 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:7:y:2016:i:1:d:10.1038_ncomms12996

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/ncomms12996

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().