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:

  1. Inevitably there is a reduction $F \leq _P D$
  2. If there was an $F \leq _P D$ reduction then F, E and D are all in the NPC class.
  3. Even if there was an $F \leq _P D$ reduction, it is still possible that $D \notin NP$.
  4. if $F \in CoNP$ then $NP \neq CoNP$
  5. 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.


if a problem is in $NPH$ then it is also in $NPC$

This statement is incorrect. A language is in $NPC$ if it is in $NPH$ and it is in $NP$.

Answer 4 is incorrect as well since that would imply that any language $L\in NP$ can be reduced to $F$, hence $L\le_p F$ and since $F\in coNP$ then $L\in coNP$. Hence, $NP\subseteq coNP$. Its not hard to show the other way around, and conclude that this means $NP=coNP$.

Answer 3 is correct. There are $NPH$ problems that is not in $NP$ (for example, take any $NEXP$-complete problem). If you choose $D=E=F\in NPH\setminus NP$ then the reductions are trivial, but they are still not in $NP$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.