# Class P is closed under rotation?

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?

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

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