Bounding the Phase Transition on Edge Matching Puzzles

摘要

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.