# If a problem A in NP is reducible in polyomial time to a problem B, can one say that B must also be in NP?

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.

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.

• That's actually an amazing answer to build up intuition. Commented Dec 22, 2023 at 12:48

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.

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.

• 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. Commented Dec 22, 2023 at 10:07

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.