The Backtracking Survey Propagation Algorithm for Solving Random K-SAT Problems
by
Raffaele Marino(Nordita and KTH)
→
Europe/Stockholm
112:028
112:028
Description
In this talk, the Backtracking Survey Propagation algorithm for solving random K-satisfiability problems with K=3,4 is presented. This new algorithm is able to find solution very close to the SAT-UNSAT threshold, in a region unreachable by any other algorithm, in a time practically linear in the problem size. 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.
The talk is mainly based on arXiv:1508.05117 (2015), [Nature Communications in press].
