Is the empty problem (or its complement) Karp reducible to any problem in NP? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-23T16:51:34Z https://cs.stackexchange.com/feeds/question/106771 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/106771 3 Is the empty problem (or its complement) Karp reducible to any problem in NP? R. dV https://cs.stackexchange.com/users/102754 2019-04-10T11:43:55Z 2019-04-10T15:56:23Z <p>I'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement:</p> <p>If <span class="math-container">$\textbf{P}=\textbf{NP}$</span>, the following holds:</p> <p>For every <span class="math-container">$A \in \textbf{NP}$</span>, there is a <span class="math-container">$B \in \textbf{NP}$</span> such that <span class="math-container">$A \leq B$</span> (where <span class="math-container">$\leq$</span> means Karp reducible).</p> <p>However, I do not understand how this applies to the empty problem <span class="math-container">$\emptyset$</span>, and it's complement <span class="math-container">$\Sigma^*$</span>, as these only have no-instances and yes-instances, respectively.</p> <p>Are there other problems in NP such that these two are reducible to them?</p> https://cs.stackexchange.com/questions/106771/-/106772#106772 3 Answer by dkaeae for Is the empty problem (or its complement) Karp reducible to any problem in NP? dkaeae https://cs.stackexchange.com/users/70382 2019-04-10T11:55:51Z 2019-04-10T15:56:23Z <p><strong>Of course there is.</strong></p> <p>Just take any non-trivial language <span class="math-container">$L$</span> (i.e., <span class="math-container">$L \neq \varnothing$</span> and <span class="math-container">$L \neq \Sigma^\ast$</span>). Then there are concrete words <span class="math-container">$x \in L$</span> and <span class="math-container">$y \not\in L$</span>.</p> <p>To reduce <span class="math-container">$\varnothing$</span> to <span class="math-container">$L$</span>, simply map <em>everything</em> to <span class="math-container">$y$</span>. Then the input is in <span class="math-container">$\varnothing$</span> (which is false) if and only if <span class="math-container">$y \in L$</span> (which is also false). Hence, the reduction is correct.</p> <p>For <span class="math-container">$\Sigma^\ast$</span>, do the same but use <span class="math-container">$x$</span> instead.</p> <hr> <p>As a note: I assume you are puzzled about <span class="math-container">$A$</span> being reduced to <span class="math-container">$B$</span>. Obviously, in the statement you cite <span class="math-container">$B$</span> should at the very least be a non-trivial set (and it seems <span class="math-container">$\textbf{P} = \textbf{NP}$</span> 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 <span class="math-container">$\varnothing$</span> or <span class="math-container">$\Sigma^\ast$</span> (and you cannot reduce either to one another, as David Richerby points out in the comments).</p> https://cs.stackexchange.com/questions/106771/-/106779#106779 1 Answer by David Richerby for Is the empty problem (or its complement) Karp reducible to any problem in NP? David Richerby https://cs.stackexchange.com/users/9550 2019-04-10T14:31:02Z 2019-04-10T14:31:02Z <p>The statement is basically vacuous. Every language is reducible to itself (the reduction is the identity function), so you can just take <span class="math-container">$B=A$</span>.</p>