Is it true that $A \leq_k B \land B \in \mathsf{coNP} \implies A \in \mathsf{coNP}$?

If so, how would you go about proving it?

  • 2
    $\begingroup$ Use the definitions. $\endgroup$ – Yuval Filmus Apr 9 at 5:05
  • 1
    $\begingroup$ @YuvalFilmus do you honestly believe your comment has any value whatsoever? $\endgroup$ – Zarwan Apr 9 at 5:58
  • 3
    $\begingroup$ @Zarwan Definitely. It has worked in the past several times. $\endgroup$ – Yuval Filmus Apr 9 at 6:03
  • $\begingroup$ @sargeras, does this answer ring a bell? $\endgroup$ – Apass.Jack Apr 9 at 6:15
  • $\begingroup$ @Apass.Jack Yes that actually does help. I wasn't initially sure if $A \leq_{k} B \implies \overline{A} \leq_{k} \overline{B}$ holds. Thanks! $\endgroup$ – sargeras Apr 9 at 20:44

Your Answer

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

Browse other questions tagged or ask your own question.