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?


Try the following construction. Given a language $L$, use $$ \{0x : x \notin L\} \cup \{1x : x \in L\}. $$

  • $\begingroup$ I'm not quite sure what you mean. Can you perhaps expand a little bit on this? $\endgroup$ – Aden Dong Oct 17 '12 at 2:42
  • 1
    $\begingroup$ Consider all possible words. Prefix those which belong to $L$ by $1$, those that don't by $0$. This may be relevant to your question. $\endgroup$ – Yuval Filmus Oct 17 '12 at 4:52

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.