Permutation reconstruction from differences (Q463039)

Summary: We prove that the problem of reconstructing a permutation \(\pi_1,\ldots,\pi_n\) of the integers \([1\ldots n]\) given the absolute differences \(|\pi_{i+1}-\pi_i|\), \(i = 1,\ldots,n-1\) is \mathsf{NP}-complete. As an intermediate step we first prove the \mathsf{NP}-completeness of the decision version of a new puzzle game that we call \textit{Crazy Frog Puzzle}. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.