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$
1
  • $\begingroup$ We can concatenate strings, not machines. $\endgroup$ Commented Dec 1, 2016 at 12:16

3 Answers 3

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$
4
  • 1
    $\begingroup$ You have to explain how you implement the first step. $\endgroup$ Commented 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
    Commented 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.
    Commented 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
    Commented Jan 9, 2023 at 11:59
2
$\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$
0
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

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