0
$\begingroup$

Is the complexity class $P$ closed under rotation, where rotation is defined as $\text{rot}(L) = \{ wv \mid vw \in L \}$? How would we prove it?

$\endgroup$
  • $\begingroup$ What did you try yourself before posting? Where did you get stuck? $\endgroup$ – David Richerby Dec 24 '13 at 13:41
5
$\begingroup$

Yes. Suppose that $L \in P$, then $x \in rot(L)$ if and only if there exist $u,v$ such that $x = uv$ and $vu \in L$.

A simple polynomial time algorithm for deciding membership in $rot(L)$ is: given the input $x =x_1 x_2 ... x_n$ generate the $n$ rotated strings $x_1 x_2 .. x_n,\, x_2 x_3 .. x_n x_1,\ldots, x_n x_1 .. x_{n-1}$ and check in polynomial time whether at least one of them belongs to $L$; in that case accept ($x \in rot(L)$) otherwise reject ($x \notin rot(L)$).

| cite | improve this answer | |
$\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.