Change search
ReferencesLink to record
Permanent link

Direct link
The backtracking survey propagation algorithm for solving random K-SAT problems
KTH, School of Computer Science and Communication (CSC), Computational Science and Technology (CST). KTH, Centres, Nordic Institute for Theoretical Physics NORDITA.ORCID iD: 0000-0002-4384-8816
2016 (English)In: Nature Communications, ISSN 2041-1723, E-ISSN 2041-1723, Vol. 7, 12996Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Nature Publishing Group, 2016. Vol. 7, 12996
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-195260DOI: 10.1038/ncomms12996ISI: 000385537300002ScopusID: 2-s2.0-84990048306OAI: oai:DiVA.org:kth-195260DiVA: diva2:1046882
Funder
Swedish Research Council, 621-2012-2982EU, European Research Council, 694925
Note

QC 20161115

Available from: 2016-11-15 Created: 2016-11-02 Last updated: 2016-11-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Marino, Raffaele
By organisation
Computational Science and Technology (CST)Nordic Institute for Theoretical Physics NORDITA
In the same journal
Nature Communications
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 11 hits
ReferencesLink to record
Permanent link

Direct link