Threshold properties of random Boolean constraint satisfaction problems

DOI10.1016/j.dam.2005.05.010zbMath1105.68051OpenAlexW1978761262MaRDI QIDQ2581551

Gabriel I. Istrate

Publication date: 10 January 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.010

zbMATH Keywords

Sharp thresholdsRandom 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)

Related Items (4)

A parametric worst-case approach to fairness in cooperative games with transferable utility ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ Statistical and algebraic analysis of a family of random Boolean equations ⋮ When does the giant component bring unsatisfiability?

Cites Work

• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Generalized satisfiability problems: Minimal elements and phase transitions.
• Models and thresholds for random constraint satisfaction problems
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• Sharp thresholds of graph properties, and the $k$-sat problem
• The phase transition in random horn satisfiability and its algorithmic implications
• Hunting for sharp thresholds
• Statistical mechanics methods and phase transitions in optimization problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Threshold properties of random Boolean constraint satisfaction problems