If P = NP, why wouldn’t \emptyset\emptyset and \Sigma^*\Sigma^* be NP-complete?

Apparently, if {\sf P}={\sf NP}, all languages in {\sf P} except for \emptyset and \Sigma^* would be {\sf NP}-complete.

Why these two languages in particular? Can’t we reduce any other language in {\sf P} to them by outputting them when accepting or not accepting?

Answer

As there are no strings in \emptyset, any machine that computes it always rejects, so we can’t map Yes-instance of other problems to anything. Similarly for \Sigma^{\ast} there’s nothing to map No-instances to.

Attribution
Source : Link , Question Author : David Faux , Answer Author : Luke Mathieson

Leave a Comment