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?

  • $\begingroup$ We can concatenate strings, not machines. $\endgroup$ Dec 1, 2016 at 12:16

2 Answers 2


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

  • 1
    $\begingroup$ You have to explain how you implement the first step. $\endgroup$ Dec 1, 2016 at 15:55
  • $\begingroup$ 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$. $\endgroup$
    – dariodip
    Dec 2, 2016 at 16:13
  • $\begingroup$ This answer is not correct in its current state. Your step 1 isn't actually implementable without some additional work or justification or explanation. $\endgroup$
    – D.W.
    Dec 3, 2016 at 1:39
  • $\begingroup$ The standard assumption is using alphabet $ \{ 0, 1 \} $ for all languages. So you can receive e.g. 10101010101001000101010 as an input word without any additional information. You will know $w$, but not $w_{1}$ or $w_{2}$, or some separator symbols. (According to your running time you expect to know this info) $\endgroup$
    – Andrii
    Jan 9 at 11:59

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.