# Is the empty problem (or its complement) Karp reducible to any problem in NP?

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?

• You don't even need to assume $P=NP$ for this. Just take $A=B$. – Tom van der Zanden Apr 10 '19 at 12:14
• Hey Tom, I think that the statement from the course meant that $\textbf{A} \neq \textbf{B}$. Otherwise, it is indeed an irrelevant requirement. – R. dV Apr 10 '19 at 12:26
• @R.dV It's irrelevant even if you assume $A\neq B$. – David Richerby Apr 10 '19 at 14:32
• @R.dV Adding to David Richerby's comment: $B \neq A$ is irrelevant since you could just take an arbitrary $A$ and set $B$ to $A$ minus a finite set (e.g., $A \setminus \{ w \}$, where $w \in A$ and $|A| > 1$) or $A$ plus a finite set not in $A$ (e.g., $A \cup \{ w \}$, where $w \not\in A$ and $A \neq \Sigma^\ast \setminus \{ w \}$). – dkaeae Apr 10 '19 at 15:59

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).

• Hey @dkaeae, thanks for responding. I thought about something like this, but as far as I knew, this wasn't correct, since we're not mapping the yes-instances from L (so, x $\in$ L) to anything in $\emptyset$, and vice versa. I don't see how we're mapping yes instances from f(I) to yes-instances of I, as there are no yes-instances of I. I learned that for any karp reduction A $\leq$ to be correct, you need two things: For I $\in$ as a yes-instance, f(i) $\in$ B should be a yes-instance, and vice versa. How could we then map f(i) yes instances to yes instances of I, if I has none? – R. dV Apr 10 '19 at 12:03
• You seem to have it the other way around. If you are reducing $\varnothing$ to $L$, then you should be mapping yes-instances of $\varnothing$ to yes-instances of $L$ and no-instances to no-instances of $L$. There are no yes-instances of $\varnothing$; hence, everything is a no-instance and we can afford mapping everything to the same no-instance $y \not\in L$. – dkaeae Apr 10 '19 at 13:12
• Yes, that's true, but we were shown that the contraposition of mapping no instances of I -> f(I) is to map yes-instances of f(I) -> I. This was ofcourse done with problems that have yes and no instances. But given your answers, I see now how it works for non-trivial languages. Thanks again :) – R. dV Apr 10 '19 at 13:52
• Re your note at the end, you can't reduce between $\emptyset$ and $\Sigma^*$, either. – David Richerby Apr 10 '19 at 14:33

The statement is basically vacuous. Every language is reducible to itself (the reduction is the identity function), so you can just take $$B=A$$.

• Hi David, Tom already commented this on the question, as I stated there, the assumption I made for this questions is that $\textbf{B}\neq\textbf{A}$ – R. dV Apr 10 '19 at 15:18
• @R.dV OK but that's your assumption and it's not included in the question you say you came across. – David Richerby Apr 10 '19 at 15:24
• Or $A$ union a finite set if $A$ is a singleton. – David Richerby Apr 10 '19 at 15:59
• Yeah that's correct David, I did not get any further context from the statement; but given the difficulty they usually propose, such a trivial answer wouldn't make a lot of sense. Anyway, your last comment does make sense, so thanks :) – R. dV Apr 10 '19 at 18:01