Question

Both P and NP are closed under operation
a) union
b) intersection
c) concatination
d) Kleene

Answer 1

Answer on Question #43230 – Math – Other

Both P and NP are closed under operation

a) union

b) intersection

c) concatenation

d) Kleene

Solution. Both sets are closed under all four operations. First we will show that $NP$ is closed under all four operations.

Assume that $L_1, L_2 \in NP$. This means that there are nondeterministic deciders $M_1$ and $M_2$ such that $M_1$ decides $L_1$ in nondeterministic time $O(n^{k_1})$ and $M_2$ deciders $L_2$ in nondeterministic time $O(n^{k_2})$.

Intersection:

$M =$ "On input $w$:

1. Run $M_1$ on $w$. If $M_1$ rejected then reject.

2. Else run $M_2$ on $w$. If $M_2$ rejected then reject.

3. Else accept."

The longest branch in any computation tree on input $w$ of length $n$ is $O(n^{\max(k_1, k_2)})$. So $M$ is a poly-time nondeterministic decider for $L_1 \cap L_2$.

Union:

$M =$ "On input $w$:

1. Run $M_1$ on $w$. If $M_1$ accepted then accept.

2. Else run $M_2$ on $w$. If $M_2$ accepted then accept.

3. Else reject."

The longest branch in any computation tree on input $w$ of length $n$ is $O(n^{\max(k_1, k_2)})$. So $M$ is a poly-time nondeterministic decider for $L_1 \cup L_2$.

Concatenation:

$M =$ "On input $w$:

1. Nondeterministically split $w$ into $w_1, w_2$ such that $w = w_1 w_2$.

2. Run $M_1$ on $w_1$. If $M_1$ rejected then reject.

3. Else run $M_2$ on $w_2$. If $M_2$ rejected then reject.

4. Else accept."

The longest branch in any computation tree on input $w$ of length $n$ is $O(n^{\max(k_1, k_2)})$. So $M$ is a poly-time nondeterministic decider for $L_1 \circ L_2$.

Kleene star:

$M =$ "On input $w$:

1. If $w = e$ then accept.

2. Nondeterministically select a number $m$ such that $1 \leq m \leq |w|$.

3. Nondeterministically split $w$ into $m$ pieces such that $w = w_1 w_2 \ldots w_m$.

4. For all $i$, $1 \leq i \leq m$: run $M_1$ on $w_i$. If $M_1$ rejected then reject.

5. Else ($M_1$ accepted all $w_i$, $1 \leq i \leq m$), accept."

The total running time is $O(n^{k_1 + 1})$. This means that $M$ is a poly-time nondeterministic decider for $L_1^*$.

The same construction can be used to prove that $P$ is closed under all four operations.

Answer: Both sets are closed under all four operations.

www.AssignmentExpert.com