# What are some known methods for showing that a class has no complete problems?

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.

• – user6973 Oct 13 '17 at 2:41
• 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. – Aryeh Oct 13 '17 at 8:37
• 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. – holf Oct 13 '17 at 8:49
• @Aryeh But not under poly-time reductions. – Emil Jeřábek Oct 13 '17 at 13:19
• 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 – Samuel Schlesinger Oct 13 '17 at 14:52