# if X is in NP but Y is not in NP then can X be reduced to Y?

I have been led to believe that the following statement

$$X \in NP \land Y \not\in NP \implies X \not\le^m_p Y$$

Is True.

But I am having difficult proving it. And I'm not even sure it IS true anymore.

At first it seemed reasonable that it was true. Since X is in NP there must exist some NP-complete problem Z that it reduces to and my thinking is that any other problem that X reduces to must also reduce to this NP-complete problem Z, that is, since X is in NP both it and any problem it can be reduced to must also reduce to an NP-complete problem Z so it cannot be the case that X can be reduced to a problem Y that is NOT in NP. This is not my proof but simply my intuition for why the statement is True.

I was hoping initially to prove it by contradiction:

suppose not, that is, suppose $$X \in NP \land Y \not\in NP$$ but $$X \le^m_p Y$$

since $$X \in NP$$ it must be that $$\exists$$ a poly-time verifier algorithm $$B$$ such that
$$\forall$$ inputs $$x \in X$$ : $$\exists$$ certificate $$t$$ s.t. $$B(x,t) = yes$$

and since $$X \le^m_p Y$$ it must be that $$\exists$$ a poly-time reduction $$f$$ such that
$$\forall$$ inputs $$x$$ $$x \in X \iff f(x) \in Y$$

it follows then that $$f(x) \in Y \iff x \in X \iff \exists t B(x,t) = yes$$

Then at this point I was hoping to reverse engineer the verifier B to come up with a poly-time verifier for Y thus contradicting the supposition that $$Y \not\in NP$$ similar to what the answer to this question does:
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
But that direction doesn't really work and I haven't found way to use the reasoning above to try and show that $$X \not\in NP$$ and achieve contradiction that way

And so this is where I am stuck. Am I missing something or am I wrong in my intuition that the statement is true?

The time hierarchy theorem states that $$\mathsf{NP}\subsetneq \mathsf{NEXP}$$.
So if you consider a $$\mathsf{NP}$$-complete problem $$A$$ (for example $$\texttt{SAT}$$) and a $$\mathsf{NEXP}$$-complete problem $$B$$ (for example $$\texttt{SUCCINCT HAMILTONIAN PATH}$$), then $$A\leqslant_m^p B$$, $$A\in \mathsf{NP}$$ and $$B\notin \mathsf{NP}$$.
Note that more simply, you can consider $$A=\emptyset$$ and $$B$$ any problem not in $$\mathsf{NP}$$ and the result still holds.
• Ah direct counter example and so the statement is false then. Could you explain what $A = \emptyset$ means? Is A literally an empty set or is this some kind of notation for A being the halting problem (I am simply not familiar with the interpretation of $\emptyset$ when discussing $P$ and $NP$) Dec 10, 2022 at 1:18
• A problem is a set. So $A = \emptyset$ means the empty problem. It can be interpreted as "the problem where the answer is always FALSE". Dec 10, 2022 at 10:28