patternMinor
Reduction from ATM to ATM-complement
Viewed 0 times
atmfromreductioncomplement
Problem
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?
(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?
Solution
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.
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.
Context
StackExchange Computer Science Q#52323, answer score: 4
Revisions (0)
No revisions yet.