World's most popular travel blog for travel bloggers.

[Solved]: Concatenation of languages in NP

, , No Comments
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 :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback