Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios

DOI10.1088/1751-8113/40/5/001zbMath1141.90587OpenAlexW1972710889MaRDI QIDQ3425245

Francesco Zamponi, Fabrizio Altarelli, Remi Monasson

Publication date: 7 March 2007

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1088/1751-8113/40/5/001

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (2)

Optimal testing for planted satisfiability problems ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT

This page was built for publication: Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios