2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – frafl
    Apr 29, 2021 at 15:00
  • $\begingroup$ Essentially, your question is very close to cs.stackexchange.com/questions/24580/… . $\endgroup$
    – frafl
    Apr 29, 2021 at 15:07
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 29, 2021 at 16:17

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.