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.

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

References in corpus (23)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• Coloring random graphs
• Survey propagation: an algorithm for satisfiability
• Algorithmic barriers from phase transitions
• Typical random 3-SAT formulae and the satisfiability threshold
• Survey Propagation as local equilibrium equations
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• On the freezing of variables in random constraint satisfaction problems
• Focused Local Search for Random 3-Satisfiability
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Survey-propagation decimation through distributed local computations
• Constraint satisfaction problems with isolated solutions are hard
• On local equilibrium equations for clustering states
• The condensation transition in random hypergraph 2-coloring
• 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
• Bicoloring Random Hypergraphs
• 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