0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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$) $\endgroup$
    – bmanicus131
    Commented Dec 10, 2022 at 1:18
  • 1
    $\begingroup$ 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". $\endgroup$
    – Nathaniel
    Commented Dec 10, 2022 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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