1
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.