# 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.

Thanks in advance.

• 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

## 2 Answers

$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.

PHPNick is right.

With A being NP we can conclude that B is atleast as hard as A if B was easier that is, if a polynomial time algorithm existed for B it could be used to solve A along with polynomial time conversion of B to A

Hence B might be p(if A is P) or NP or NP-hard or NP-complete While if A is NP B has to be atleast NP or it could be NP-hard or NP-complete