patternMinor
Is the empty problem (or its complement) Karp reducible to any problem in NP?
Viewed 0 times
problemtheanyemptyreducibleitscomplementkarp
Problem
I'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement:
If $\textbf{P}=\textbf{NP}$, the following holds:
For every $A \in \textbf{NP}$, there is a $B \in \textbf{NP}$ such that $A \leq B$ (where $\leq$ means Karp reducible).
However, I do not understand how this applies to the empty problem $\emptyset$, and it's complement $\Sigma^*$, as these only have no-instances and yes-instances, respectively.
Are there other problems in NP such that these two are reducible to them?
If $\textbf{P}=\textbf{NP}$, the following holds:
For every $A \in \textbf{NP}$, there is a $B \in \textbf{NP}$ such that $A \leq B$ (where $\leq$ means Karp reducible).
However, I do not understand how this applies to the empty problem $\emptyset$, and it's complement $\Sigma^*$, as these only have no-instances and yes-instances, respectively.
Are there other problems in NP such that these two are reducible to them?
Solution
Of course there is.
Just take any non-trivial language $L$ (i.e., $L \neq \varnothing$ and $L \neq \Sigma^\ast$). Then there are concrete words $x \in L$ and $y \not\in L$.
To reduce $\varnothing$ to $L$, simply map everything to $y$. Then the input is in $\varnothing$ (which is false) if and only if $y \in L$ (which is also false). Hence, the reduction is correct.
For $\Sigma^\ast$, do the same but use $x$ instead.
As a note: I assume you are puzzled about $A$ being reduced to $B$. Obviously, in the statement you cite $B$ should at the very least be a non-trivial set (and it seems $\textbf{P} = \textbf{NP}$ is redundant, as Tom van der Zanden notes in the comments; in fact, the statement is rather fishy, see David Richerby's answer); note you cannot reduce non-trivial sets to $\varnothing$ or $\Sigma^\ast$ (and you cannot reduce either to one another, as David Richerby points out in the comments).
Just take any non-trivial language $L$ (i.e., $L \neq \varnothing$ and $L \neq \Sigma^\ast$). Then there are concrete words $x \in L$ and $y \not\in L$.
To reduce $\varnothing$ to $L$, simply map everything to $y$. Then the input is in $\varnothing$ (which is false) if and only if $y \in L$ (which is also false). Hence, the reduction is correct.
For $\Sigma^\ast$, do the same but use $x$ instead.
As a note: I assume you are puzzled about $A$ being reduced to $B$. Obviously, in the statement you cite $B$ should at the very least be a non-trivial set (and it seems $\textbf{P} = \textbf{NP}$ is redundant, as Tom van der Zanden notes in the comments; in fact, the statement is rather fishy, see David Richerby's answer); note you cannot reduce non-trivial sets to $\varnothing$ or $\Sigma^\ast$ (and you cannot reduce either to one another, as David Richerby points out in the comments).
Context
StackExchange Computer Science Q#106771, answer score: 3
Revisions (0)
No revisions yet.