3
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You don't even need to assume $P=NP$ for this. Just take $A=B$. $\endgroup$ – Tom van der Zanden Apr 10 at 12:14
  • $\begingroup$ Hey Tom, I think that the statement from the course meant that $\textbf{A} \neq \textbf{B}$. Otherwise, it is indeed an irrelevant requirement. $\endgroup$ – R. dV Apr 10 at 12:26
  • 1
    $\begingroup$ @R.dV It's irrelevant even if you assume $A\neq B$. $\endgroup$ – David Richerby Apr 10 at 14:32
  • $\begingroup$ @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 \}$). $\endgroup$ – dkaeae Apr 10 at 15:59
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – R. dV Apr 10 at 12:03
  • $\begingroup$ 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$. $\endgroup$ – dkaeae Apr 10 at 13:12
  • $\begingroup$ 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 :) $\endgroup$ – R. dV Apr 10 at 13:52
  • $\begingroup$ Re your note at the end, you can't reduce between $\emptyset$ and $\Sigma^*$, either. $\endgroup$ – David Richerby Apr 10 at 14:33
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – R. dV Apr 10 at 15:18
  • $\begingroup$ @R.dV OK but that's your assumption and it's not included in the question you say you came across. $\endgroup$ – David Richerby Apr 10 at 15:24
  • $\begingroup$ Or $A$ union a finite set if $A$ is a singleton. $\endgroup$ – David Richerby Apr 10 at 15:59
  • $\begingroup$ 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 :) $\endgroup$ – R. dV Apr 10 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.