Question

Show that $\mathit{N}\mathit{P}$is closed under union and concatenation.

Short answer

$T$is a poly-time non-deterministic decider for $A^{°}B$

Step-by-step solution

The class NP is closed under union & Concatenation

$NP-class:NP$is a class of languages that are decidable in nondeterministic polynomial time on a non – deterministic Turing machine.

To Union of diagram

Let $A andB$be languages are decided by $NP-$ machines $T_A$and $T_B$. Now we want to show that, there is a non – deterministic poly time decider $T_{A\cup B}$ that decides union of $A andB$The construction of $T_{A\cup B}$is as follows:

$T_{A\cup B}=$On input $S$ :

1. Run $T_A$on $S$. If$T_A$ accepts$S$ , then accept.

2. Else run $T_B$on S. If accepts$S$ , then accept.

3. Else reject”

As the new TM $T_{A\cup B}$calls $T_A$and $T_B$each once, it runs on $O(T_A+T_B)$,

as both are NP is $T_{A\cup B}$

To Concatenation the languages

Let $A andB$be languages are decided by$NP$machines $T_A$and $T_B$. Now we want to show that, there is a non – deterministic poly time decider$T_{A\cup B}$ that decides concatenation of$A andB$.The construction of $T_{A°B}$ is as follows:

$T_{A°B}$=On input $S$:

1.$S$Split into $S_1$,$S_2$ such that $S=S_1,S_2$.

2. Run the $T_B$on$S_2$ . If${\mathit{T}}_{\mathbf{B}}$ is rejected, then reject.

3. Else accept.

Thus, $T$is a poly-time non-deterministic decider for $A^{°}B$.