[Solved]: Concatenation of languages in NP

Problem Detail: 

I have a hard time to understand why the concatenation of two languages over an alphabet (concatenation is in NP), doesn't imply that each of the languages for themselves are in NP. I talked with my Prof about the problem today, but I can't wrap my head around it. Can you help me out?

Asked By : but_they_should

Answered By : David Richerby

Take the concatenation of $\Sigma^*$ with any language that contains the empty word but is known not to be in NP (for example, an undecidable language).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33034

3.2K people like this

 Download Related Notes/Documents