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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.