patternMinor
Are all decidable languages mapping reducible to its complement?
Viewed 0 times
allarelanguagesreducibledecidableitscomplementmapping
Problem
I dont think this is true, take the language with a single element L = {0}, then the complement L' would have infinitely many strings (everything that isn't 0). So if it were true that A is mapping reducible to its complement, everything in L' can be obtained via a computable function from some element in L, i.e 010 is in L' however there is no x in L that gives f(x) = 101, since theres only one element, 0, it maps to one result.
Would this be correct?
Would this be correct?
Solution
Let $L_1,L_2$ be two languages over $\{0,1\}$. A (computable) mapping reduction from $L_1$ to $L_2$ is a computable function $f\colon \{0,1\}^ \to \{0,1\}^$ such that for all $x \in \{0,1\}^*$ it holds that $x \in L_1$ iff $f(x) \in L_2$.
In your example, $L_1 = \{0\}$ and $L_2 = \overline{\{0\}}$, there does exist a mapping reduction, given by
$$
f(x) = \begin{cases} 1 & \text{if }x = 0, \\ 0 & \text{if }x \neq 0.\end{cases}
$$
Clearly $f$ is computable, and you can check that $x \in L_1$ iff $f(x) \in L_2$.
Hence your example doesn't work. You can check, however, that $\emptyset$ and $\{0,1\}^*$ are two examples of languages not reducible to their complement. Indeed, these are the only examples, which you can try to prove.
In your example, $L_1 = \{0\}$ and $L_2 = \overline{\{0\}}$, there does exist a mapping reduction, given by
$$
f(x) = \begin{cases} 1 & \text{if }x = 0, \\ 0 & \text{if }x \neq 0.\end{cases}
$$
Clearly $f$ is computable, and you can check that $x \in L_1$ iff $f(x) \in L_2$.
Hence your example doesn't work. You can check, however, that $\emptyset$ and $\{0,1\}^*$ are two examples of languages not reducible to their complement. Indeed, these are the only examples, which you can try to prove.
Context
StackExchange Computer Science Q#76710, answer score: 4
Revisions (0)
No revisions yet.