Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length
type: Item
instance of: scholarly article
title: Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length
author: Wei Xu
author: Zhe Zhang
author: Guangyan Zhou
published in: Physica A
publication date: 2023-01-17T00:00:00Z
Mathematics Subject Classification ID: 82-XX
zbMATH DE Number: 7642801
zbMATH Keywords: constraint satisfaction problem
zbMATH Keywords: solution space structure
zbMATH Keywords: phase transition
zbMATH Keywords: problem hardness
zbMATH Keywords: belief propagation
MaRDI profile type: Publication
full work available at URL: j.physa.2022.128367
OpenAlex ID: W4310431054
cites work: Q3184605
cites work: Information, Physics, and Computation
cites work: Random constraint satisfaction: Flaws and structure
cites work: Principles and Practice of Constraint Programming – CP 2004
cites work: Q3624064
cites work: Constructing an asymptotic phase transition in random binary constraint satisfaction problems
cites work: The satisfiability threshold for randomly generated binary constraint satisfaction problems
cites work: Q4954175
cites work: On the phase transitions of random \(k\)-constraint satisfaction problems
cites work: A general model and thresholds for random constraint satisfaction problems
cites work: Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
cites work: Random constraint satisfaction: easy generation of hard (satisfiable) instances
cites work: The solution space structure of planted constraint satisfaction problems with growing domains
cites work: Quiet Planting in the Locked Constraint Satisfaction Problems
cites work: Q5715725
cites work: Theory and Applications of Satisfiability Testing
cites work: Q3624048
cites work: Two solutions to diluted \(p\)-spin models and XORSAT problems
cites work: Gibbs states and the set of solutions of random constraint satisfaction problems
cites work: On the freezing of variables in random constraint satisfaction problems
cites work: Survey propagation: An algorithm for satisfiability
cites work: On the solution-space geometry of random constraint satisfaction problems
cites work: On the solution‐space geometry of random constraint satisfaction problems
cites work: On the constraint length of random \(k\)-CSP
cites work: Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP
cites work: On the survey-propagation equations in random constraint satisfiability problems
cites work: Survey propagation as local equilibrium equations
DOI: 10.1016/J.PHYSA.2022.128367
description: scientific article; zbMATH DE number 7642801