Satisfiability of large random Boolean formulas with K variables per clause (random K-satisfiability) is a fundamental problem in combinatorial discrete optimization. Here we study random K -satisfiability for K = 3, 4 by the Backtracking Survey Propagation (BSP) algorithm, which is able to find, in a time almost linear in the problem size, solutions within a region never reached before: for K = 3 the algorithmic threshold practically coincides with the SAT-UNSAT threshold, while for K=4 it extrapolates beyond the rigidity threshold, where most of the solutions acquire a positive density of frozen variables. All solutions found by BSP have no frozen variables, thus supporting the conjecture that only unfrozen solutions can be found in linear time. The iterative algorithm for determining which variables are frozen in a solution (whitening) reaches the all-variables-unfrozen fixed point following a two step process and has a relaxation time diverging at the algorithmic threshold.
from cs.AI updates on arXiv.org http://ift.tt/1I5Y6A4
via IFTTT
No comments:
Post a Comment