Show that NP is closed under concatenation

Question

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?

Answer 1

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$.

Answer 2

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.