The phase transition in random regular exact cover

DOI10.4171/AIHPD/31zbMath1353.68210arXiv1502.07591MaRDI QIDQ329450

Moore, Cristopher

Publication date: 21 October 2016

Published in: Annales de l'Institut Henri Poincaré D. Combinatorics, Physics and their Interactions (AIHPD) (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.07591

zbMATH Keywords

phase transitionsNP-complete problemssatisfiabilityBoolean formulasrandom structuressecond moment methodsmall subgraph conditioning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) 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 (5)

On the number of solutions in random hypergraph 2-colouring ⋮ Charting the replica symmetric phase ⋮ The satisfiability threshold for random linear equations ⋮ Unnamed Item ⋮ On the Number of Solutions in Random Graphk-Colouring

This page was built for publication: The phase transition in random regular exact cover