I have a question in complexities that I could not do.
There will be D, E, F, three languages belonging to NPH. Suppose that the reductions exist $D \leq _P E$ and $E \leq _P F$. Determine which of the following statements is correct:
- Inevitably there is a reduction $F \leq _P D$
- If there was an $F \leq _P D$ reduction then F, E and D are all in the NPC class.
- Even if there was an $F \leq _P D$ reduction, it is still possible that $D \notin NP$.
- if $F \in CoNP$ then $NP \neq CoNP$
- None of the above claims are true.
I think the answer is probably 2, because there are reductions between all the problems. So everyone should be in $NPH$, and if a problem is in $NPH$ then it is also in $NPC$. I can not understand why 4 is not true, it also seems logical.