On the phase transitions of random \(k\)-constraint satisfaction problems

DOI10.1016/j.artint.2010.11.004zbMath1216.68243OpenAlexW2046178780MaRDI QIDQ543632

Yun Fan, Jing Shen

Publication date: 17 June 2011

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2010.11.004

zbMATH Keywords

phase transitionconstraint satisfaction problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ The scaling window of the model \(d\)-\(k\)-CSP ⋮ Fractional Edge Cover Number of Model RB ⋮ On the phase transitions of \((k, q)\)-SAT ⋮ The maximum happy induced subgraph problem: bounds and algorithms ⋮ Bounding the scaling window of random constraint satisfaction problems ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ Large hypertree width for sparse random hypergraphs ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length ⋮ On the constraint length of random \(k\)-CSP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Generalized satisfiability problems: Minimal elements and phase transitions.
• Structure of large random hypergraphs
• A sharp threshold for a random constraint satisfaction problem
• Satisfiability threshold for random XOR-CNF formulas
• Many hard examples in exact phase transitions
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• An empirical study of phase transitions in binary constraint satisfaction problems
• Locating the phase transition in binary constraint satisfaction problems
• Models and thresholds for random constraint satisfaction problems
• Sharp thresholds of graph properties, and the $k$-sat problem
• Dependent Sets of Constant Weight Binary Vectors
• Hunting for sharp thresholds
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• Classifying the Complexity of Constraints Using Finite Algebras
• Probability and Computing
• The satisfiability threshold for randomly generated binary 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