MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
+1. Great question! – Joel David Hamkins Jul 7 '13 at 1:47
i think you should sort sequence into ascending order and if you sum adjacent elements and get distinct elements in the list then it could be difference of some not it? – dato datuashvili Jul 7 '13 at 6:39
I'm not sure that I get your idea. Do you a have an algorithm? – Mohammad Al-Turkistany Jul 7 '13 at 8:49
The problem is NP complete it is not NP hard.It can be reduced to (in fact it is equivalent to) boolean SAT. The good news may be that your particular version just may not be in the list of NP complete problems – ARi Jul 8 '13 at 5:56
@ARi Could you give a reference or explanation for your claim. Also, this should then be an answer. – Christian Stump Jul 8 '13 at 6:22
up vote 11 down vote accepted

I tried to give a formal proof of the NP-completeness of the problem.

For the reduction details see my answer on

share|cite|improve this answer
I am looking forward to the addictive smartphone-app version of the Crazy Frog puzzle! – Per Alexandersson Oct 27 '14 at 12:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.