HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

If A is reducible to its complement, is the converse true as well?

Submitted by: @import:stackexchange-cs··
0
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.