Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
3  
+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 permutation.is 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
1  
@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
show 6 more comments

1 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

share|improve this answer
add comment

Your Answer

 
discard

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.