The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem
From MaRDI portal
Publication:2910950
DOI10.1137/090777268zbMath1277.68217arXiv1202.0042OpenAlexW2010957786MaRDI QIDQ2910950
No author found.
Publication date: 12 September 2012
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1202.0042
Random graphs (graph-theoretic aspects) (05C80) Phase transitions (general) in equilibrium statistical mechanics (82B26) Error analysis and interval analysis (65G99) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (4)
Many hard examples in exact phase transitions ⋮ The satisfiability threshold for random linear equations ⋮ On the uniformity of the approximation for $r$-associated Stirling numbers of the second Kind ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
This page was built for publication: The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem
