patternMinor
Find an undecidable language that is mapping-reducible to its complement
Viewed 0 times
undecidablereduciblelanguageitsthatfindcomplementmapping
Problem
As the title suggests. Also, such a language must satisfy that neither it nor its complement are semi-decidable. I already know that $All_{TM}, EQ_{TM}, T$ (that is the set of all deciders) satisfy this property. But I tried reducing these to their complements directly, and via some sort of intermediate language, but to no avail. Can anyone help?
Solution
Another more advanced answer is to look at a complete problem from a class that is closed under complement. For example, take the arithmetical hierarchy which is closed under complements. Now consider a complete problem for it like:
Given: a sentence in the language of first-order arithmetic,
Question: is the sentence true (in the standard model $\mathbb{N}$)?
It is easy that one can reduce this to its complement by negating the sentence.
This works generally for any class that is closed under completion and has a complete problem (w.r.t. many-one reductions).
Given: a sentence in the language of first-order arithmetic,
Question: is the sentence true (in the standard model $\mathbb{N}$)?
It is easy that one can reduce this to its complement by negating the sentence.
This works generally for any class that is closed under completion and has a complete problem (w.r.t. many-one reductions).
Context
StackExchange Computer Science Q#6100, answer score: 2
Revisions (0)
No revisions yet.