The only way that I know of is the way that you can show that $RE \cap coRE$ does not via diagonalization. Mostly curious because if $NP \cap coNP$ has no complete problems then $P \neq NP$. I tried to use that diagonalization method a while ago to no avail but I never really asked about other methods.

  • 1
    $\begingroup$ mathoverflow.net/a/27612/5810 ​ ​ $\endgroup$
    – user6973
    Oct 13, 2017 at 2:41
  • $\begingroup$ Can you elaborate on the $RE\cap coRE$ claim? The latter is just $R$, and all non-trivial languages in $R$ are equivalent under mapping reductions -- so in a sense, every language is complete. $\endgroup$
    – Aryeh
    Oct 13, 2017 at 8:37
  • 2
    $\begingroup$ Another technique which is the same idea as in Ricky's comment: if PH has a complete problem then the hierarchy collapse at some level. This is a usual technique for hierarchies. $\endgroup$
    – holf
    Oct 13, 2017 at 8:49
  • 1
    $\begingroup$ @Aryeh But not under poly-time reductions. $\endgroup$ Oct 13, 2017 at 13:19
  • $\begingroup$ Yeah, sorry, I should have mentioned that. I'll prove it for first order reductions: say we have a language $L$ complete for $RE \cap coRE$ under first order reductions. We enumerate all first order reductions $f_i$ and we define $A_i = \{ x \mid f_i(x) \in L \}$. Clearly $A_i$ accounts for all languages in $RE \cap coRE$. However, we can define $D = \{ i \mid f_i(i) \notin L \}$, which is also in $RE \cap coRE$, but $\exists i, A_i = D$ is a contradiction, and thus we have our result. @Aryeh $\endgroup$ Oct 13, 2017 at 14:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.