Let P $ \neq $ NP. D is in the complexity class co-NP. B is in the complexity class P. Let $ \bar{D} $ be the complement of D, then $\bar{D} $ $\leq _ {p} $ B.

Is this statement true or false? My guess is that it's wrong because D is $ \in $ co-NP and therefore $\bar{D} $ is $ \in $ NP. From the reduction $\bar{D}$ $ \leq_ {p} $B, it would follow that P = NP, which contradicts to the assumption.

Is that correct or am I having a mistake?

  • 1
    $\begingroup$ D and B could just be in P. $\endgroup$ – Yuval Filmus Feb 28 '19 at 6:59
  • $\begingroup$ Can you explain why D could be in P? Does that mean if D is in co-np, that the complement of D is not in NP? $\endgroup$ – user101036 Feb 28 '19 at 7:13
  • $\begingroup$ @x_x Because D is simply in coNP, not coNP-complete. $\endgroup$ – dkaeae Feb 28 '19 at 7:27
  • $\begingroup$ But isn't coNP all problems, that have a complement in NP? $\endgroup$ – user101036 Feb 28 '19 at 12:06

Your Answer

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