Prove that L $\in$ NP implies L* $\in$ NP I have been trying to solve this problem with witness theorem. So the problem is as below: 
Define $L^* := \{x \in \Sigma^*|$there exists k and $x_1,...,x_k\in L$ such that $x=x_1x_2...x_k\}$. Prove that $L \in NP$ implies $L^* \in NP$. 

So my initial thought is to find a witness language $\in P$ for $L^*$ from the fact that L has a witness language L1 $\in P$. However, I am not sure how to find the right partition of x such that I can use the witness $(x_1,y_1),...,(x_k,y_k) \in L1$. 

Does anyone have any thought on it? Much appreciated!
Lets hop back to the definition of a NP language, there exists a non-deterministic Turing machine NTM that halts when given $x$. 

It's not that much work to create a non-deterministic Turing machine that first splits the input string into parts non-deterministically and then simulates running NTM on each of the parts and only halts when all parts make the NTM halt.