My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is NP-complete. I searched the literature without finding an equivalent or close problem.


Originally motivated by this post, [Can you identify the sum of two permutations in polynomial time?](https://cstheory.stackexchange.com/questions/18037/can-you-identify-the-sum-of-two-permutations-in-polynomial-time/18045#18045) , and my interest in computational properties of permutations.


A differences sequence $a\_1, a\_2, \ldots a\_n$ of a permutation $\pi$ of numbers $1, 2, \ldots n+1$ is formed by finding the difference between every two adjacent numbers in the permutation $\pi$. In other words, $a\_i= |\pi(i+1)-\pi(i)|$ for $1 \le i \le n$


For example, sequence $1, 1, 3$ is the differences sequence of permutation $2 3 4 1$. While, sequences $2, 2, 3$ and $ 3, 1, 2$ are not the differences sequence of any permutation of numbers $1, 2, 3, 4$. 



> 
> Is there an efficient algorithm to determine whether a given sequence is the differences sequence for some permutation $\pi$, or is it NP-hard?
> 
> 
> 


We get computationally equivalent problem if we formulate the problem using circular permutations.


Cross posted on TCS SE without an answer. [Efficient algorithm for existence of permutation with differences sequence?](https://cstheory.stackexchange.com/questions/18255/efficient-algorithm-for-existence-of-permutation-with-differences-sequence)


**EDIT** Marzio's nice NP-completeness proof has been published in the [Electronic Journal of Combinatorics](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p3).



How hard is reconstructing a permutation from its differences sequence?
I tried to give a formal proof of the NP-completeness of the problem.


For the reduction details see my answer on [cstheory.stackexchange.com](https://cstheory.stackexchange.com/questions/18255/efficient-algorithm-for-existence-of-permutation-with-differences-sequence/18345#18345)


