Show NP is closed under "relabelling"

Question

This is an interesting question I'm stuck with:

Define a relabelling to be a function $\phi : \Sigma \to \Sigma$ (not necessarily a bijection).

If $x = x_1 \ldots. x_n$ is a string, we define $\varphi(x) = \varphi(x_1)φ=\varphi(x_2) \ldots \varphi(x_n)$.

If $L$ is a language, we define $\varphi(L) = \{\varphi(x) : x \in L\}$.

Show that if a language $L$ is in NP, and $\varphi$ is a relabelling, then $\varphi(L) \in \text{NP}$.

Thanks in advance!

Answer 1

Here is one way to do it:

Let $M$ be a nondeterministic poly-time Turing machine for $L$; we build a nondeterministic poly-time Turing machine $N$ for $\varphi(L)$:

• On input $y = y_1 y_2 \ldots y_n$, first nondeterministically guess the original string $x = x_1 x_2 \ldots x_n$. First, check if $\varphi(x_1) \varphi(x_2) \ldots \varphi(x_n) = y_1 y_2 y_3 \ldots y_n$; if not, immediately reject. If so, run $M$ on $x$.

Can you explain why this works?