Show that set of words in NP

Question

Let ∈ NP. How can I show that the set of all cyclic permutations of words from also lies in NP

The issue I have with this task is that I cannot understand the correlation of cyclic permutation as a component of A to the NP prove itself

Answer 1

There are two common (and equivalent) definitions of the NP class: one involving non-deterministic Turing Machines, and another one using certificates. I will work with the second one here.

I suppose we work on an alphabet $\Sigma$. A language $L$ is in the class NP if there exists a deterministic TM $M$, working in polynomial time, and a polynomial $p$ such that

$\forall x \in \Sigma^\ast,\; x \in L \Leftrightarrow \exists y \in \Sigma^{p(|x|)},\; M$ accepts the input $(x, y)$

Said differently, there exists a certificate $y$ of polynomial size that "helps" the machine decide whether your word is in the language or not. For example, in the 3-COLOR problem (deciding whether or not a graph is 3-colourable), such a $y$ could be the encoding of a valid colouring.

In your case, you know that all the aforementioned objects exist ($M, p \dots$). You simply have to slightly modify them: to the certificate $y$, you add some information to tell which permutation of your input is in $A$ (for example, if we note by $\sigma$ the simple cyclic permutation moving each letter to the left, you just add $n$ at the end of the certificate if $\sigma^n(x) \in A$. Now, you modify the machine so that on input $(x, y|n)$, it first computes $\sigma^n(x)$ and then runs as before on this modified input. Everything thing is still polynomial, and so $\{\sigma^n(x) | n \in \mathbb N, x \in A\} \in $NP