6
$\begingroup$

Is there a reduction from ATM to ATM-complement?

(ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$)

I have been thinking about it too much and couldn't find the answer.

I know that reduction from ATM-complement to ATM is not possible becouse if it was, ATM would not be in RE. But how can I proove/profe the other way around?

$\endgroup$
4
$\begingroup$

By the very same reason you have mentioned there cannot be such a (many-one) reduction.

Note that if you have two problems, say $A$ and $B$, and $A\le_m B$ then also $\bar A \le_m \bar B$. In fact the same reduction can be used for both statements. So a reduction from ATM to ATM-complement, would also be a reduction from ATM-complement to ATM. And you already know that such a thing does not exist.

If you are however ask for Turing reduction, then the answer is yes. We can ask an ATM oracle and invert the answer to get a Turing machine that decides ATM-complement.

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