Bounding the Phase Transition on Edge Matching Puzzles
Authors:
- Ramón BéjarRBRamón Béjar
- César FernandezCFCésar Fernandez
- Carles MateuCMCarles Mateu
- Nuria PascualNPNuria Pascual
- 1 May 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0195623X,p. 80-85
Abstract
Edge matching puzzles have been, for a very long time, a common toy for children. Their simplicity hides a subtle and complex problem structure that results, in certain cases, in very hard problems. Those hard cases are being commercially exploited, capturing a wide attention due to generous prizes. Edge matching puzzles have been proven to be NP-Complete problems, and their phase transition has been recently located experimentally. This work approaches the problem of defining and locating the phase transition for edge matching puzzles from an analytical point of view, defining statistical measures that; on one hand, upper bound the phase transition and prove to be good estimators for locating the hardest problems, and on the other hand, approaches the lower bound of the phase transition as a previous step to determine an exact asymptotic behavior.Keywords
This publication has 11 references indexed in Scilit:
- Edge Matching Puzzles as Hard SAT/CSP Benchmarks2008
- Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and ComplexityGraphs and Combinatorics, 2007
- Random k‐SAT: Two Moments Suffice to Cross a Sharp ThresholdSIAM Journal on Computing, 2006
- Hiding Satisfying Assignments: Two are Better than OneJournal of Artificial Intelligence Research, 2005
- Rigorous location of phase transitions in hard optimization problemsNature, 2005
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)Journal of the American Mathematical Society, 2004
- Approximating the unsatisfiability threshold of random formulasRandom Structures & Algorithms, 1998
- An empirical study of phase transitions in binary constraint satisfaction problemsArtificial Intelligence, 1996
- Critical behavior in the computational cost of satisfiability testingArtificial Intelligence, 1996
- The complexity of theorem-proving procedures1971