Show that if $\mathbf{P}=\mathbf{NP}$ , then every language$\mathbf{A}\mathbf{\in }\mathbf{P}$ , except $\mathbf{A}\mathbf{=}\mathbf{\varnothing }\mathbf{and}\mathbf{A}\mathbf{=}\mathbf{\Sigma }\mathbf{\ast }$, is $\mathbf{NP}\mathbf{-}$ complete.

The class $\mathrm{NP}$ is significant because it contains a large number of practical issues. Both $\mathrm{HAMPATH}\&\mathrm{COMPOSITES}$ seem to be members of $\mathrm{NP}$, as shown in the preceding discussion. $\mathrm{COMPOSITES}$ also is a member of $P$ , which is a subset of $\mathrm{NP}$, as we indicated; nevertheless, establishing this stronger result is considerably more difficult.

Even though all acceptable pseudorandom computer models are polynomially comparable, the class $\mathrm{NP}$is unaffected by the model chosen. We use the same rules for describing and analysing nondeterministic polynomial time algorithms as we use for deterministic polynomial time algorithms.

A vocabulary $\mathrm{B}\mathrm{is}\mathrm{said}\mathrm{to}\mathrm{be}\mathrm{NP}-\mathrm{complete}$if all of the previous conditions are met:

NP is indeed a category of systems that can be solved in polynomial time on a nondeterministic Turing machine; alternatively, to put it another way, it is a class of languages whose membership can be validated in polynomial time. $\mathrm{P}$ is a category of languages in which membership can be determined in polynomial time.