# How far would complexity hierarchies collapse if $L\in CoNP$ is $L\in NPH$?

Let $$L\in CoNP$$. Assuming that $$L\in NPH$$, what would we get?

So, as $$L\in NPH$$ then every language $$A\in NP$$ has a reduction $$A \leq L$$. This would mean that $$\overline{L} \leq L$$ as well. By reduction properties the same reduction applies for: $$L\leq \overline{L}$$. So $$\overline{L}\in NPH$$ and thus $$\overline{L}\in NPC$$.

Now lets take any $$M \in CoNPH$$. By definition: $$L \leq M$$. By transitivity $$M \in NPH$$. This would generally apply that $$CoNPH \subseteq NPH$$.

But these are the only conclusions I was able to come up with.

I'm certain there are other things to conclude from here, any ideas? Will such a thing really collapse several omplexity hierarchies, or will it not be such a big change?

Additional conclusions 1: Let $$B\in CoNP$$. Since $$L \in NPH$$ then: $$\overline{B} \leq L$$. The same reduction means that: $$B \leq \overline{L}$$. This means $$\overline{L} \in CoNPH$$.

Let $$N\in NPH$$. By definition: $$\overline{L} \leq N$$ (As $$\overline{L}\in NP$$). Recall $$B\in CoNP$$. By transitivity $$B \leq N$$. Thus, $$N \in CoNPH$$. Meaning $$NPH \subseteq CoNPH$$.

Together with what we discovered previously, we get $$NPH = CoNPH$$.

Is this really such a big deal? After all, having $$NPH = CoNPH$$ does not mean $$NP = CoNP$$. Are there any more conclusions to have here?

Additional conclusions 2: Recall that: $$L,\overline{L} \in NPH, CoNPH$$. Let $$A \in NP$$. By definition: $$A \leq L$$. Denote $$M_{L,CoNP}$$ a deterministic TM which, for an input $$w \in\Sigma^*$$, given a polynomial size hint, reaches (in polnymoial time) an accepting state if $$x\notin L$$ (this is the definition of $$L \in CoNP$$). We will show $$A\in CoNP$$ by constructing a TM $$M_{A,CoNP}$$. For a given input $$x\in\Sigma^*$$, the TM $$M_{A,CoNP}$$ works the following steps:

1. Convert $$x$$ to $$f(x)$$ by the reduction function $$f:A \rightarrow L$$.
2. Run $$M_{L,CoNP}$$ on $$f(x)$$.
3. Return the same answer.

It can be shown by the properties of the reduction $$f$$ and of the TM $$M_{L,CoNP}$$ that the TM $$M_{A,CoNP}$$ works properly. This means that $$A\in CoNP$$.

This means that $$NP \subseteq CoNP$$.

A symmetric proof shows that $$CoNP \subseteq NP$$.

Together, it means that $$NP = CoNP$$. So this is (to my opinion) a bigger discovery. Together with $$NPH = CoNPH$$ it means also that $$NPC = CoNPC$$. Are there are more things to conclude from here? How far can we collapse possible complexity classes? I don't think we can conclude something about $$P$$ from all this, though.