HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

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

Submitted by: @import:stackexchange-cs··
0
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?

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.