Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length

DOI10.1016/j.physa.2022.128367OpenAlexW4310431054MaRDI QIDQ2111656

Zhe Zhang, Guangyan Zhou, Wei Xu

Publication date: 17 January 2023

Published in: Physica A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.physa.2022.128367

zbMATH Keywords

phase transitionconstraint satisfaction problembelief propagationproblem hardnesssolution space structure

Mathematics Subject Classification ID

Statistical mechanics, structure of matter (82-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A general model and thresholds for random constraint satisfaction problems
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP
• On the constraint length of random \(k\)-CSP
• On the freezing of variables in random constraint satisfaction problems
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Survey propagation as local equilibrium equations
• Information, Physics, and Computation
• On the survey-propagation equations in random constraint satisfiability problems
• Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
• The solution space structure of planted constraint satisfaction problems with growing domains
• Survey propagation: An algorithm for satisfiability
• Gibbs states and the set of solutions of random constraint satisfaction problems
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Theory and Applications of Satisfiability Testing
• On the solution-space geometry of random constraint satisfaction problems
• On the solution‐space geometry of random constraint satisfaction problems
• Principles and Practice of Constraint Programming – CP 2004
• Random constraint satisfaction: Flaws and structure
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems