An empirical study of phase transitions in binary constraint satisfaction problems

DOI10.1016/0004-3702(95)00048-8OpenAlexW2023722467WikidataQ63549371 ScholiaQ63549371MaRDI QIDQ2674179

Patrick Prosser

Publication date: 22 September 2022

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

Full work available at URL: https://doi.org/10.1016/0004-3702(95)00048-8

zbMATH Keywords

hard problemsmushy regionsearch phase transitionsempirical study of phase transition behavior in CSPsrandom binary constraint satisfaction problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (18)

Partition search for non-binary constraint satisfaction ⋮ Range and Roots: two common patterns for specifying and propagating counting and occurrence constraints ⋮ Modelling and solving temporal reasoning as propositional satisfiability ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ Phase transitions and the search problem ⋮ Refining the phase transition in combinatorial search ⋮ Locating the phase transition in binary constraint satisfaction problems ⋮ Graph representation of the fixed route dial-a-ride problem ⋮ On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. ⋮ Hybrid search for minimal perturbation in dynamic CSPs ⋮ A CSP search algorithm with responsibility sets and kernels ⋮ Concurrent search for distributed CSPs ⋮ An optimal coarse-grained arc consistency algorithm ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Constructing an asymptotic phase transition in random binary constraint satisfaction problems ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ Backtracking algorithms for disjunctions of temporal constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Experimental evaluation of preprocessing algorithms for constraint satisfaction problems
• The hardest constraint problems: A double phase transition
• Exploiting the deep structure of constraint problems
• Easy problems are sometimes hard
• Locating the phase transition in binary constraint satisfaction problems
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Needed: An Empirical Science of Algorithms
• Backtrack Programming

This page was built for publication: An empirical study of phase transitions in binary constraint satisfaction problems