No easy puzzles: Hardness results for jigsaw puzzles
We model jigsaw puzzle solving and study the number of edge matchings required. Realistic jigsaw puzzles require ?(n2) ? ( n 2 ) comparisons in the worst case. Realistic jigsaw puzzles require ?(n2) ? ( n 2 ) comparisons on average. Generalised puzzles require (tightly) O(n2) O ( n 2 ) and ?(nlog?n) ? ( n log ? n ) comparisons.
jigsaw puzzle parsimonious testing communication complexity subgraph isomorphism