0
$\begingroup$

If you are given two languages $A$, $B$ and $$A \leq_T B.$$ Is it possible to $\overline{A} \leq_T B$ or $A \leq_T \overline{B}$?

Here is my shot.

Case 1: $\overline{A} \leq_T B$

This is only possible if $A \leq_m B$ exists and $B=\overline{B}$. As you can transform any many-one reduction to its complement, we can show that if $A \leq_m B$, then $\overline{A} \leq_m \overline{B}=B$. Thus $\overline{A} \leq_m B$.

Case 2: $A \leq_T \overline{B}$

This is the same as above but we need to change the role of $A$ and $B$.

$\endgroup$
2
$\begingroup$

You say:

This is only possible if $A \le_m B$ exists and $B=\overline{B}$

But that condition simplifies to "false" since it can never the case that $B=\overline{B}$.

Anyway the answer to both cases is "yes". If $A \le_T B$ then there is a Turing machine $T$ with oracle $B$ that decides $A$. By complementing $T$'s output we obtain a Turing machine with oracle $B$ that decides $\overline{A}$ showing that $\overline{A} \le_T B$. Moreover, consider a Turing machine $T'$ with oracle $\overline{B}$ that simulates $T$ except for the following: whenever $T$ invokes its oracle for $B$ on some input $w$, $T'$ invokes its oracle for $\overline{B}$ on $w$ and then complements the result. Clearly $T'$ still decides $A$, thus showing that $A \le_T \overline{B}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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