Permutation Reconstruction from Differences

Abstract

We prove that the problem of reconstructing a permutation $\pi_1,\dotsc,\pi_n$ of the integers $[1\dotso n]$ given the absolute differences $|\pi_{i+1}-\pi_i|$, $i = 1,\dotsc,n-1$ is $\sf{NP}$-complete. As an intermediate step we first prove the $\sf{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.

An addendum was added to this paper on the 9th of December 2015.