0
$\begingroup$

i.e. $A\leq_pB\:\wedge\:B\in\text{co-NP}\rightarrow A\in\text{co-NP}$ ?

I feel like it's the case but I can't think of a straightforward proof.

Clarification: I am talking about polynomial-time Turing reductions.

$\endgroup$
15
  • $\begingroup$ Do you know how to solve this with coNP replaced by NP? If so, try connecting the two. $\endgroup$ Commented Apr 19, 2021 at 5:47
  • $\begingroup$ @YuvalFilmus It seems not. I know there are a few questions about this here but none of the answers make sense to me. For example, cs.stackexchange.com/questions/128187/… here there only seems to be a question of a 1-to-1 reduction. But a polynomial-time reduction can have multiple calls to problem B, not only one. $\endgroup$
    – nc404
    Commented Apr 19, 2021 at 14:52
  • $\begingroup$ Are you sure the reduction is not many-one? $\endgroup$ Commented Apr 19, 2021 at 15:30
  • $\begingroup$ @YuvalFilmus What do you mean? In that problem? It says the reduction is "x in X iff phi(x) in Y", that's a single call to Y, isn't it? $\endgroup$
    – nc404
    Commented Apr 19, 2021 at 15:39
  • $\begingroup$ So the reduction in your case is many-one. You mentioned that "a polynomial-time reduction can have multiple calls to problem B", but this is not the case here. $\endgroup$ Commented Apr 19, 2021 at 15:41

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.