3
$\begingroup$

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. Here, I propose another computational problem which I highly suspect that it is 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.e. $\pi(i)= \tau(i+k \mod n) \circ \tau(i)$).

I did not find a notion of shift product for permutations in the literature.

Formally,

Square Permuation

Instance: A permutation $\pi$ of $1, 2, \ldots n$

Question: Is permutation $\pi$ a square for the shift product?

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$.

This was posted on mathOverflow.

$\endgroup$
  • $\begingroup$ I guess you mean $\pi(i)=\tau(\tau(i)+k \mod n)$. Otherwise it makes little sense. Maybe a better notation: let's write $[k]\pi$ the $k$-shift of $\pi$. The question is then: is there a $\tau$ such that $\pi=[k]\tau \circ \tau$? $\endgroup$ – Marc Sep 27 '15 at 22:49
  • $\begingroup$ @Marc Let $\tau(i)$=[2,4,1,6,5,3] then $\tau(i+1)$=[4,1,6,5,3,2]. The shift product $\tau(i+1) \circ \tau(i)$=[1,5,4,2,3,6]. – Mohammad Al-Turkistany 2 hours ago $\endgroup$ – Mohammad Al-Turkistany Sep 28 '15 at 11:08
4
$\begingroup$

It's really quite easy. Let $$\rho_k = \left( \begin{matrix}1&2&\ldots&n\\ (k+1)\bmod n&(k+2)\bmod n&\ldots&(k+n)\bmod n\end{matrix} \right)$$ be the shift permutation. Then the shift of $\tau$ is just $\sigma = \tau \circ \rho_k$, and the shift product of $\tau$ is $\tau \circ \rho_k \circ \tau$. But $$\pi = \tau \circ \rho_k \circ \tau \iff \rho_k \circ \pi = (\rho_k \circ \tau)^2$$

Given $\pi$ you can find $\rho_k \circ \pi$ in linear time, and then you just need to see whether it has a square root, which can also be done in linear time.

$\endgroup$

Your Answer

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

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