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

arXiv: https://arxiv.org/abs/1508.05117 · HTML: https://mlsanity.com/paper/1508.05117/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Aug 2015.

## Built on by (most cited first, 14 of 14)

- [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023)
- [Phase transitions in the mini-batch size for sparse and dense two-layer neural networks](https://mlsanity.com/paper/2305.06435/) (2023)
- [Complex Recurrent Spectral Network](https://mlsanity.com/paper/2312.07296/) (2023)
- [Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems](https://mlsanity.com/paper/2309.05337/) (2023)
- [Fast Analysis of the OpenAI O1-Preview Model in Solving Random K-SAT Problem: Does the LLM Solve the Problem Itself or Call an External SAT Solver?](https://mlsanity.com/paper/2409.11232/) (2024)
- [Recurrent neural networks that generalize from examples and optimize by dreaming](https://mlsanity.com/paper/2204.07954/) (2022)
- [Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems](https://mlsanity.com/paper/2602.18419/) (2026)
- [Nonlocal Monte Carlo via Reinforcement Learning](https://mlsanity.com/paper/2508.10520/) (2025)
- [A residual-based message passing algorithm for constraint satisfaction problems](https://mlsanity.com/paper/2202.12468/) (2022)
- [Engineered Ordinary Differential Equations as Classification Algorithm (EODECA): thorough characterization and testing](https://mlsanity.com/paper/2312.14681/) (2023)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)
- [Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints](https://mlsanity.com/paper/2506.15774/) (2025)
- [A Geometric Perspective on the Difficulties of Learning GNN-based SAT Solvers](https://mlsanity.com/paper/2508.21513/) (2025)
- [Perfect reconstruction of sparse signals using nonconvexity control and one-step RSB message passing](https://mlsanity.com/paper/2512.17426/) (2025)

## Abstract (arXiv)

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.