3
$\begingroup$

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?

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

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

$\endgroup$
  • 1
    $\begingroup$ You have to explain how you implement the first step. $\endgroup$ – Yuval Filmus Dec 1 '16 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$ – darioSka Dec 2 '16 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 '16 at 1:39
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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