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

DOI10.1016/J.PHYSA.2022.128367MaRDI QIDQ2111656OpenAlexFDO

Authors Wei Xu, Zhe Zhang, Guangyan Zhou

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

• scientific article; zbMATH DE number 5547880 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• scientific article; zbMATH DE number 2243408 (Why is no real title available?)
• A general model and thresholds for random constraint satisfaction problems
• Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
• Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems
• Generating hard satisfiable formulas by hiding solutions deceptively
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Handbook of constraint programming.
• Information, Physics, and Computation
• On the constraint length of random \(k\)-CSP
• On the freezing of variables in random constraint satisfaction problems
• On the phase transitions of random \(k\)-constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• On the survey-propagation equations in random constraint satisfiability problems
• Principles and Practice of Constraint Programming – CP 2004
• Quiet planting in the locked constraint satisfaction problems
• Random constraint satisfaction: Flaws and structure
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Survey propagation as local equilibrium equations
• Survey propagation: An algorithm for satisfiability
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• The solution space structure of planted constraint satisfaction problems with growing domains
• Theory and Applications of Satisfiability Testing
• Two solutions to diluted \(p\)-spin models and XORSAT problems

This page was built for publication: Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111656)