<p>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.</p>

CC BY-SA 3.0
2017-10-13T08:37:49.467Z
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
CC BY-SA 3.0
2017-10-13T08:49:30.193Z
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
CC BY-SA 3.0
2017-10-13T13:19:39.093Z
@Aryeh But not under *poly-time* reductions.
Emil Jeřábek
CC BY-SA 3.0
2017-10-13T14:52:31.617Z
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
<cc.complexity-theory><np><p-vs-np>
What are some known methods for showing that a class has no complete problems?
Samuel Schlesinger
# What are some known methods for showing that a class has no complete problems?

(Asked by: username_0 on 2017-10-13)

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.

**Tags:** cc.complexity-theory, np, p-vs-np

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: @username_1 But not under *poly-time* reductions.  
> **username_0**: 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.  @username_1  

---

## 0 answers

