2
$\begingroup$

I need to show that assuming $NP \neq coNP$ then there are 2 non-trivial languages $A$ and $B$ ($A,B \neq \emptyset, \Sigma^*$) in $NP \cup coNP$ such that there's no polynomial time reduction from A to B and there's no polynomial time reduction from B to A.

I tried doing this:
Let $A$ be non-trivial language such that $A \in NP \implies \bar{A} \in coNP$, let's suppose to the contrary that there is a polynomial reduction such that $A \leq_p \bar{A}$.
From $A \leq_p \bar{A}$ it follows that $\bar{A} \leq_p A$. Since $A\in NP$ we can conclude that $\bar{A} \in NP$.
Then by definition if $\bar{A} \in NP \implies A\in coNP$. Therefore $NP = coNP$. Contradiction.

I also tried picking 2 languages from $NP\cup coNP$ such that $A$ is NP-complete and $B$ is $coNP$ and to show that if one of the cases ($A \leq_p B$ or $B \leq_p A$) is true then it leads to a contradiction, but I got stuck showing that the case $B \leq_p A$ where $B \in coNP$ and $A \in NP-complete$ yields contradiction.

I'll appreciate any insights, thanks.

$\endgroup$

1 Answer 1

2
$\begingroup$

The first attempt is not really helpful because you can pick a nontrivial language $A\in \text{P}$ (a too easy language), and in this case, one can easily obtain a PTIME reduction from $A$ to its complement. Can you tell why? So this gives no contradiction. What you need to do is aim to the big fish, languages that are complete in NP, and those that are complete in coNP -- your second attempt.

So consider an $\text{NP-complete}$ language $A$, for example $A = SAT$, and consider its complement $\overline{A}$, which is $\text{coNP-complete}$. If by contradiction there is a PTIME reduction from $A$ to its complement, that is $A\leq_p \overline{A}$, then the fact that $A$ is $\text{NP-hard}$ and transitivity of PTIME reductions, imply that $L \leq_p \overline{A}$, for every language $L\in \text{NP}$. Now as $\overline{A}\in \text{coNP}$, we get that $L$ is in $\text{coNP}$ as well. So we've shown that $\text{NP}\subseteq \text{coNP}$, and thus reached a contradiction.

So what you were missing is the following standard claim:

Claim: If $A \leq_p B$, and $B$ is in $\text{NP}$ ($\text{coNP}$), then $A$ is in $\text{NP}$ ($\text{coNP}$, respectively).

The intuition is that if you want to collapse one class into another, for example collapse $\text{NP}$ into $\text{coNP}$ and show that $\text{NP}\subseteq \text{coNP}$, then it is sufficient to find a problem in $\text{coNP}$ that is harder than an NP-complete problem (one of the hardest problems in $\text{NP}$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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