A probabilistic analysis of randomly generated binary constraint satisfaction problems.

DOI10.1016/S0304-3975(02)00317-1zbMath1055.68102DBLPjournals/tcs/DyerFM03OpenAlexW2013181989WikidataQ56323957 ScholiaQ56323957MaRDI QIDQ1401196

D. Massart

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00317-1

Mathematics Subject Classification ID

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

Related Items (5)

Many hard examples in exact phase transitions ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ The scaling window of the model \(d\)-\(k\)-CSP ⋮ 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

Cites Work

• Unnamed Item
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• Sudden emergence of a giant \(k\)-core in a random graph
• A Sufficient Condition for Backtrack-Free Search

This page was built for publication: A probabilistic analysis of randomly generated binary constraint satisfaction problems.