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? , 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?
EDIT Marzio's nice NP-completeness proof has been published in the Electronic Journal of Combinatorics.
Best Answer
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