Random constraint satisfaction: Flaws and structure

DOI10.1023/A:1011454308633zbMath0992.68193OpenAlexW2071706116MaRDI QIDQ5949019

Ewan Macintyre, Ian Philip Gent, Patrick Prosser, Toby Walsh, Barbara M. Smith

Publication date: 12 November 2001

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1011454308633

zbMATH Keywords

random graphsstructured graphs

Mathematics Subject Classification ID

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

Related Items (30)

Many hard examples in exact phase transitions ⋮ Partition search for non-binary constraint satisfaction ⋮ On the Integration of Singleton Consistencies and Look-Ahead Heuristics ⋮ The impact of search heuristics on heavy-tailed behaviour ⋮ Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ The solution space structure of planted 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 ⋮ Combinatorial sharpness criterion and phase transition classification for random CSPs ⋮ Interleaving solving and elicitation of constraint satisfaction problems based on expected cost ⋮ Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs ⋮ Dealing with satisfiability and \(n\)-ary CSPs in a logical framework ⋮ On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. ⋮ Is computational complexity a barrier to manipulation? ⋮ New algorithms for bidirectional singleton arc consistency ⋮ Explorative anytime local search for distributed constraint optimization ⋮ Another look at the phenomenon of phase transition ⋮ Elicitation strategies for soft constraint problems with missing preferences: properties, algorithms and experimental studies ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ Constructing an asymptotic phase transition in random binary constraint satisfaction problems ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ A new branch-and-filter exact algorithm for binary constraint satisfaction problems ⋮ Reasoning from last conflict(s) in constraint programming ⋮ When does the giant component bring unsatisfiability? ⋮ Resolution complexity of random constraint satisfaction problems: Another half of the story ⋮ Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length

This page was built for publication: Random constraint satisfaction: Flaws and structure