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.
1
$\begingroup$
$\endgroup$
-
2$\begingroup$ 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$. $\endgroup$ – ttnick May 17 '18 at 18:36
1
$\begingroup$
$\endgroup$
$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.
1
$\begingroup$
$\endgroup$
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
