# Is $A \leqslant_P B \iff A \in \mathsf{P}^B$? If not are there counter-examples?

The way I think of reducing problem $$A$$ to problem $$B$$ in polynomial time, i.e. $$A \leqslant_P B$$, is that you assume an efficient solution to $$B$$ which is enough to solve $$A$$. Now, this is suspiciously similar to $$A \in \mathsf{P}^B$$. I'm confident that $$A \leqslant_P B \implies A \in \mathsf{P}^B$$ but is the reverse implication true? If not, can you provide some counter examples?

Similarly can anything be said about the statement: $$A \leqslant_L B \iff A \in \mathsf{L}^B$$

Edit: Clarified $$\leqslant_P$$ is polynomial reduction and fixed notation for PTIME, LOGSPACE.

• Thanks, but there is still one thing missing: are you talking about many-one reductions, i.e., $\exists f\in \mathsf{FP}: x\in A\iff f(x) \in B$ (FP contains functions computable in polynomial time)? Then the answer below is correct, if you consider Turing reductions both expressions are synonyms. Your first sentence sounds more like Turing reductions. Apr 29, 2021 at 15:00
• Essentially, your question is very close to cs.stackexchange.com/questions/24580/… . Apr 29, 2021 at 15:07
• @frafl I am considering many-one polynomial reductions. But yes, it is the closeness of these ideas that caused me to investigate if there was some overlap. Thanks for the question, I will check it out. Apr 29, 2021 at 16:17

Assuming $$\le_P$$ is a polynomial many-one reduction (as opposed to a Turing reduction), the statement is incorrect.
For example, for any language $$L$$ we have $$\overline{L} \in P^L$$ (and in fact, in $$O(1)$$ time and space as well, so this is also an example for logspace many-one reductions)
But obviously if we take $$L=\mathrm{Halt}$$ to be the halting problem language, we wont have that $$\overline{L} \le_P L$$ since $$\mathrm{Halt}\in \mathsf{RE}$$ but $$\overline{\mathrm{Halt}}\notin \mathsf{RE}$$ and $$\mathsf{RE}$$ is closed under $$\le_P$$.