Pairs of SAT-assignments in random Boolean formulæ

DOI10.1016/j.tcs.2008.01.005zbMath1136.68049arXivcond-mat/0506053WikidataQ61444433 ScholiaQ61444433MaRDI QIDQ2481970

Marc Mézard, Riccardo Zecchina, Thierry Mora, Hervé Daudé

Publication date: 15 April 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cond-mat/0506053

zbMATH Keywords

clustering; satisfiability

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Finite size scaling for the core of large random hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Supersaturated graphs and hypergraphs
• The 3-XORSAT threshold.
• The phase transition in a random hypergraph
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• On the dynamics of the glass transition on Bethe lattices
• Phase transitions and the search problem
• Coloring Random Graphs
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Sharp thresholds of graph properties, and the $k$-sat problem
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Hunting for sharp thresholds
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• Geometrical organization of solutions to random linear Boolean equations
• Survey propagation: An algorithm for satisfiability
• Theory and Applications of Satisfiability Testing
• Determining computational complexity from characteristic ‘phase transitions’
• Threshold values of random K‐SAT from the cavity method
• The complexity of theorem-proving procedures
• On the solution-space geometry of random constraint satisfaction problems