2
$\begingroup$

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.

$\endgroup$
1

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.