Non-deterministic Turing machine for $L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$

Question

Show if L is in NP, then also L1 is in NP

$$L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$$

I know that if L is in NP, then there exists a NTM $M_L$ than accepts $x$, with $|x|=n$. I can use $M_L$ to describe an NTM $N$ for $L_1$. I have a problem by understanding which is the best non-deterministic operation in $N$ to create an $x$ string for $L$.

Answer 1

Let us describe an NTM $N$ that computes $L_1$ in polynomial time. The machine "guesses" the first $n - |w|$ letters of a word $x'$ (it makes all possible guesses non-deterministicly) and append $w$ to $x'$ then it simulates $M$ on the resulting word. If $M$ accepts on any of the guesses the machine $N$ halts and accepts. If all reject, $N$ also rejects.

Since, we have $n$ zeroes as a part of the input, the guesses are done in linear time in the size of the input. The simulation also runs in polynomial time in an NTM by assumption, hence, we get a total polynomial running itme and hence, $L_1$ is in NP. The correctness of $N$ is straight forward.