# Show that NP is closed under concatenation

Show that NP is closed under concatenation.

This is a homework problem and I would appreciate some guidance. I began by saying the following:

Let $A$ and $B$ exist in NP. Let $V_1$ and $V_2$ be verifiers for $A$ and $B$, respectively.

Is it as simple as saying build two NTMs $M_1$ and $M_2$ that decide $A$ and $B$ and then concatenate them and build a new machine to decide?

• We can concatenate strings, not machines. – Hans Hüttel Dec 1 '16 at 12:16

The easiest way to prove that NP is closed under concatenation is the following:

Assume that $L_1 , L_2 \in NP$. Thus, there are two nondeterministic deciders $M_1$ and $M_2$ such that $M_1$ decides $L_1$ in nondeterministic time $O(n^l)$ and $M_2$ decides $L_2$ in nondeterministic time $O(n^k)$.
Let $M$ a TM s.t.

$M$ on input $w$:

1. Split $w$ into $w_1 \in L_1$ and $w_2 \in L_2$ s.t. $w = w_1 w_2$;
2. Run $M_1$ on $w_1$. If $M_1$ rejects then reject;
3. Else run $M_2$ on $w_2$, if $M_2$ rejects then reject;
4. Else accept.

This will use $O(n^{\max{l,k}})$ steps. So $M$ is a polytime nondeterministic decider for $L_1L_2$.

• You have to explain how you implement the first step. – Yuval Filmus Dec 1 '16 at 15:55
• We assumed that we know $w_1$ and $w_2$ and then $w = w_1 w_2$. Tecnically we could write them on the tape as $w_1 \# w_2$ if $\# \notin \Gamma$. – darioSka Dec 2 '16 at 16:13
• This answer is not correct in its current state. Your step 1 isn't actually implementable without some additional work or justification or explanation. – D.W. Dec 3 '16 at 1:39

No, it's not that simple. You need to explain what you mean by concatenate $$M_1$$ and $$M_2$$. The machines $$M_1,M_2$$ don't output strings that can be concatenated.

You need to describe what the concatenated machine $$M$$ does. On input $$x$$, how does it use the machines $$M_1,M_2$$? If you run $$M_1,M_2$$ on the entire input $$x$$ it won't help you to decide the concatenated language, so you'll have to be more industrious.