patternMinor
If A is reducible to its complement, is the converse true as well?
Viewed 0 times
thereducibletrueconverseitswellcomplement
Problem
I was reading a proof that said that if $A \le_{m} \bar{A}$, then it can be inferred that $\bar{A} \le_{m} A$ as well. Is this a logical conclusion, and if so, why? I didn't think this followed with languages A and B, but if B is A's complement, can one make such a statement?
Solution
In general whenever $A\le_m B$ via computable function $f$, we automatically have $\bar{A}\le_m \bar{B}$ via the same $f$. The reason is that $x\in A\iff f(x) \in B$ implies that $x \in \bar{A} \iff f(x) \in \bar{B}$.
Context
StackExchange Computer Science Q#14967, answer score: 6
Revisions (0)
No revisions yet.