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
