# If a decision problem $A \in \text{NP}$ and there exists reduction so that $A \leq_p B$, for decision problem B, what can be deduced about B?

I think that it implies that B can be solved by a non-deterministic polynomial time or worse Turing machine, but I realise that there is possibly some greater result that I'm missing.

• This is a very vague question. $A$ might be in $\mathsf{P}$. In this case you have gained no information about $B$ at all. If $A$ is complete for $\mathsf{NP}$ then you know that $B$ is $\mathsf{NP}$-hard. But this is no proof that there is no deterministic polynomial time Turing machine deciding $B$. – ttnick May 17 '18 at 18:36

$B$ cannot be the language $\emptyset$ or the language $\Sigma^*$. Apart from that, you can conclude absolutely nothing about $B$.
So, the given condition doesn't rule out anything useful about $B$; just about everything remains possible. $B$ could be in $P$, or it could be in $NP$, it could be harder than anything in $NP$; you can't rule any of those out.