Permutation Reconstruction from Differences

Abstract

We prove that the problem of reconstructing a permutation ${\pi }_1,\dots ,{\pi }_n$ of the integers $[1\dots n]$ given the absolute differences $|{\pi }_{i+1}-{\pi }_i|$, $i=1,\dots ,n-1$ is NP-complete. As an intermediate step we first prove the NP-completeness of the decision version of a new puzzle game that we call Crazy Frog Puzzle. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.

22 pages, appears in The Electronic Journal of Combinatorics 21(4) (2014); #P4.3