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.


Your Answer

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

Browse other questions tagged or ask your own question.