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

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.

11 pages, 10 figures. v2: data largely improved and manuscript rewritten

References in corpus (12)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Survey propagation: an algorithm for satisfiability
• Typical random 3-SAT formulae and the satisfiability threshold
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• On the freezing of variables in random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• On local equilibrium equations for clustering states
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• A backtracking survey propagation algorithm for K-satisfiability
• The large deviations of the whitening process in random constraint satisfaction problems
• Some remarks on the survey decimation algorithm for K-satisfiability

Cited by in corpus (26)

• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Biased landscapes for random Constraint Satisfaction Problems
• The large deviations of the whitening process in random constraint satisfaction problems
• Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
• Hard Optimization Problems have Soft Edges
• Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Revisiting the Challenges of MaxClique
• A theory of non-equilibrium local search on random satisfaction problems
• Phase transitions in the mini-batch size for sparse and dense two-layer neural networks
• Sum of squares lower bounds for refuting any CSP
• Optimal segmentation of directed graph and the minimum number of feedback arcs
• Streamlining Variational Inference for Constraint Satisfaction Problems
• Maximally flexible solutions of a random $K$-satisfiability formula
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Realizing interdependent couplings as thermal or higher-order interactions
• A residual-based message passing algorithm for constraint satisfaction problems
• The solution space structure of planted constraint satisfaction problems with growing domains
• Order-to-chaos transition in the hardness of random Boolean satisfiability problems
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Interacting Copies of Random Constraint Satisfaction Problems
• Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints