Question

Show that $\mathbf{NP}$ is closed under the star operation

Short answer

Therefore, $NP$ is closed under star operation.

Step-by-step solution

Randomized of P

On such a randomized single cassette Turing machine, $P$ is a class of languages that can be deduced in polynomial time. Let $L$ become the language chosen by the $\mathrm{NP}$ machine to demonstrate that is closed under star operation.

To determine $L*$ in non-deterministic polynomial time, we'll use a non-deterministic Turing machine $\mathrm{N}$ .

Create N

The creation of $\mathrm{N}$ is discussed in the phases that follow.

$\mathrm{N}=\mathrm{On}\mathrm{input}\mathrm{w}:$

1. If $\mathrm{w}=\mathrm{E}$ , accept.
2. Split $\mathrm{w}\mathrm{into}\mathrm{k}$ parts in an ad hoc manner.

$\mathrm{w}={\mathrm{w}}_1,{\mathrm{w}}_2,{\mathrm{w}}_3,\dots {\mathrm{w}}_{\mathrm{k}}$

1. Discover the credentials that display non-deterministically for each ${\mathrm{w}}_1$. Check the certifications for authenticity.
2. Approve if verification has been completed; otherwise, refuse if verification has not been completed.

A non-deterministic Turing machine $\mathrm{N}$ that determines $L*$ in non-deterministic polynomial time. For each ${\mathrm{w}}_1$ guess the certificates that determine non deterministically. Verify the certificates.

• If verification $\mathrm{k}$ done then accept ,
• Else reject if verification fails.

Here, we constructed a non deterministic turing machine $\mathrm{N}\mathrm{that}\mathrm{decides}\mathrm{L}*$ in non deterministic polynomial time.

Hence, $NP$ is closed under star operation.