0
$\begingroup$

In other words:

If $A \leq_{p} B$ and $A \in NP \Rightarrow B \in NP$

From my deduction this is has to be false. We know that if $A$ is NP Complete $\Rightarrow A$ NP-Hard and $A \in NP$, then $B$ is NP-Hard but we can't say for sure that $B \in NP$.

I struggle to understand why though.

$\endgroup$

4 Answers 4

3
$\begingroup$

Just to give you some kind of image you can use to build your intuition:

Think of the problems and the complexity classes, as boxes and shipping containers of different shapes and sizes. Translate $A \leq_p B$ to "box $A$ fits into box $B$", and translate $A \in \mathrm{NP}$ to "box $A$ fits into shipping container $\mathrm{NP}$".

If you know that

  • box $A$ fits into box $B$, and that
  • box $A$ fits into shipping container $\mathrm{NP}$,

can you conclude that box $B$ fits into shipping container $\mathrm{NP}$? You can't, right? Box $B$ might be too big or weirdly shaped to fit in there.

$\endgroup$
1
  • 1
    $\begingroup$ That's actually an amazing answer to build up intuition. $\endgroup$
    – me5ng3
    Commented Dec 22, 2023 at 12:48
1
$\begingroup$

One rough intuition that can help you is: if $A \leq_p B$, then $A$ is "simpler than or equal to" $B$.

The fact that there exists a (polynomial) reduction $A \mapsto B$ tells you that $A$ is either the same problem as $B$ or a special case of it. In this sense, $A \leq_p B$ does not tell you anything about $B$ in general.

In a case such as $SAT \leq B$, however, you know that $SAT$ is $\mathcal {NP}$-Hard, which means (using the intuition above) that every problem in $\mathcal{NP}$ is "simpler" than $SAT$. By the transitive property of $\leq$, it is immediate that every $\mathcal {NP}$ problem is also "simpler" than $B$, which means that $B$ is $\mathcal{NP}$-Hard as well.

If, additionally, we knew that $B$ is in $\mathcal{NP}$, we could conclude that it is $\mathcal{NP}$-complete.

$\endgroup$
1
$\begingroup$

Any $B$ such that $B$ is $\text{NP}$-hard but not $\text{NP}$-complete suffices as a counterexample. By definition, any $A\in\text{NP}$ can be reduced to such a $B$ in polynomial time.

One choice for $B$ would be the Halting-Problem $H$. Clearly $H\not\in\text{NP}$, though $H$ is $\text{NP}$-hard.

$\endgroup$
1
  • $\begingroup$ Thanks for your answer! Yes, I know how to prove this with by contradiction, but I do not understand intuitively why this stands without just giving a circular definition of what is already known. $\endgroup$
    – me5ng3
    Commented Dec 22, 2023 at 10:07
1
$\begingroup$

If you can reduce A in polynomial time to B then B might be much more difficult than A, including being much harder. “Polynomial reduction” means if you can solve the B instance then you get a solution for the A instance, so the harder B is, the easier it will be to reduce A to B.

It may be possible that the instances of B that you create by reducing instances of A are all in NP, but that might not be helpful.

$\endgroup$

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.