Concatenation of two languages in NP

Question

I have a hard time to understand why the concatenation of two languages over an alphabet, which 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?

Answer 1

Here's a counterexample to the claim that if A and B are languages and AB ∈ NP, then A ∈ NP and B ∈ NP. First, consider all subsets of the set 1*. There are countably infinitely many strings in 1*, so there are uncountably many subsets of 1*. Since there are only countably many decidable languages, at least one of these languages is undecidable; let's have that language be A. For B, choose 1*.

My claim is that AB is some language of the form { 1ⁿ | n ≥ k } for some natural number k. To see this, let k be the length of the shortest string in A. Then any string in AB has the form 1^k+m1^r, where 1^k+m ∈ A and 1^r ∈ B. Such a string necessarily belongs to { 1ⁿ | n ≥ k }. Similarly, if we take any string from { 1ⁿ | n ≥ k }, we can see that it has the form 1^k+m = 1^k1^m, where 1^k ∈ A and 1^m ∈ B. Therefore, AB = { 1ⁿ | n ≥ k }.

The language AB is regular because it's given by the regular expression 1^k1*, but A is not in NP because it's undecidable and all languages in NP are decidable.

Hope this helps!