Concatenation of languages in NP 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?
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).