Polynomial hierarchy, many-one reduction, but with co-NP subroutine

Question

Let's say I have three problems, problem A is $\Sigma_{2}^{P}$-complete, problem B is co-NP-complete and problem C $\in \Sigma_{2}^{P}$.

In a many-one reduction from A to C (i.e. showing hardness for C), could I polynomially often use B (e.g. as a subroutine) to construct the equivalent C instance?

Is that a valid way to show hardness (if we e.g. assume co-NP $\subseteq \Sigma_{2}^{P}$ is strict), or does the co-NP-completeness of B make this reduction "non-polynomial"?

Answer 1

What you have is an $\mathsf{FP^{NP}}$ reduction. This is not known to imply the existence of a proper polynomial-time reduction; it's weaker. However, it still shows $C$ is "hard" in much the same way: in particular, $C$ is not in $\Delta^P_2$ unless $\mathsf{PH}=\Delta^P_2$, and it is not in $\Pi^P_2$ unless $\mathsf{PH}=\Sigma^P_2\cap\Pi^P_2$. (All the classes $\Sigma^P_n$, $\Pi^P_n$, $\Delta^P_n$ for $n\ge2$, as well as PH, PSPACE, EXP, ..., are closed under $\mathsf{FP^NP}$ reductions.)

• TRH: Thanks, if I understand it correctly it is a stronger result (because it is weaker) than a Cook reduction - which would be $\mathsf{FP^{C}},ドル right? In a proof, is it preferrable to use the stronger reduction to the more common one? I hope this doesn't drift too far into the meta/philosophical aspects.
• Emil Jeřábek: As far as I can tell, the existence of a polytime Turing (Cook) reduction is incomparable to the existence of an $\mathsf{FP^{NP}}$ many-one reduction. Neither implies the other.