This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation problem (How hard is reconstructing a permutation from its differences sequence?) which turned out to be NP-complete.

The shift of a permutation $\pi(i)$ of numbers $1, 2, \ldots n$ is defined as $\sigma(i)$= $\pi(i+k \mod n)$ for some fixed $k$, $1 \le k \lt n$. The shift product of a permutation $\pi$ is defined as $ \pi(i+k \mod n) \circ \pi(i)$. We say that a permutation $\pi$ is a square for the shift product if there is a permutation $\tau$ such that $\pi$ is the shift product of $\tau$. I did not find a notion of shift product for permutations in the literature.

Is there an efficient algorithm to determine whether a given permutation $\pi$ is a square for the shift product of some permutation $\tau$, or is it NP-complete?

The problem appears to be hard even when the shift amount $k=1$.

EDIT: I posted this on TCS SE.

  • $\begingroup$ I wonder if the shift product function is a good candidate for an average-case one-way permutations (or at least in the worst-case). $\endgroup$ – Mohammad Al-Turkistany Sep 24 '15 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.