The Complexity of Crazy Frog Puzzle and Permutation Reconstruction from Dierences
Marzio De Biasi · 2013
We prove that the problem of reconstructing a permutation 1;:::; n of the integers [1:::n] given the absolute dierences j i+1 ij, i = 1;:::;n 1 is NP{complete. As an intermediate step we rst prove the NP{completeness of the decision version of a new puzzle game that we call Crazy Frog Puzzle. The permutation reconstruction problem is one of the simplest arithmetic problems that has been proved to be computationally intractable.