# If a problem A has a poly-time reduction to a problem B in co-NP, is A in co-NP as well?

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.

• Do you know how to solve this with coNP replaced by NP? If so, try connecting the two. Commented Apr 19, 2021 at 5:47
• @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. Commented Apr 19, 2021 at 14:52
• Are you sure the reduction is not many-one? Commented Apr 19, 2021 at 15:30
• @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? Commented Apr 19, 2021 at 15:39
• 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. Commented Apr 19, 2021 at 15:41