patternMajor
If P = NP, why wouldn't $\emptyset$ and $\Sigma^*$ be NP-complete?
Viewed 0 times
whyandwouldncompletesigmaemptyset
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#7453, answer score: 28
Revisions (0)
No revisions yet.