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?
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$:
- Split $w$ into $w_1 \in L_1$ and $w_2 \in L_2$ s.t. $w = w_1 w_2$;
- Run $M_1$ on $w_1$. If $M_1$ rejects then reject;
- Else run $M_2$ on $w_2$, if $M_2$ rejects then reject;
- Else accept.
This will use $O(n^{\max{l,k}})$ steps. So $M$ is a polytime nondeterministic decider for $L_1L_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.
Proof: If L1,L2∈NP then there exist a deterministic polynomial verifier for L1 and a deterministic polynomial verifier for L2. A polynomial verifier for L1⋅L2 will receive a split “index” (a natural number) of the input w to w1 and w2. The verifier for L1⋅L2 runs L1 verifier on w1 and L2 verifier on w2. Since the verifiers are deterministic and run in polynomial time, we can run them in series and check their answer. If they both accept, the verifier for L1⋅L2 accepts. Otherwise, it rejects.
