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 '17 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 '17 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 '17 at 8:49
  • 1
    $\begingroup$ @Aryeh But not under poly-time reductions. $\endgroup$ – Emil Jeřábek Oct 13 '17 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$ – Samuel Schlesinger Oct 13 '17 at 14:52

Your Answer

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

Browse other questions tagged or ask your own question.