<p>Disclaimer: this is not a direct answer. </p>

<p>Actually there are many more hardness conditions other than P != NP and the UGC. David Johnson <a href="http://davidsjohnson.net/columns/col25.pdf" rel="nofollow">wrote a beautiful column</a> for the Transactions on Algorithms back in 2006 on precisely this issue. He lists out the numerous different assumptions that are used to show hardness, and how they relate to each other. </p>

<p>Unfortunately, these are all NP vs deterministic classes (with the exception of NP and co-AM). NP vs co-NP is not covered at all. </p>

CC BY-SA 2.5
2010-10-20T04:28:47.780Z
As an interesting aside, David Johnson DOES talk about NP vs co-NP in the very next column -- [NP-completeness column number 26](http://www2.research.att.com/~dsj/columns/col26.pdf)!
Daniel Apon
CC BY-SA 2.5
2010-10-20T04:33:22.613Z
ah of course. I should have remembered. But no approximations though...
Suresh Venkat
CC BY-SA 3.0
2010-10-20T04:12:27.933Z
2015-09-09T23:29:49.290Z
2015-09-09T23:29:49.290Z
Suresh Venkat
<p>$NP \ne coNP$ is a stronger hypothesis than $P \ne NP$ since $NP\ne coNP$ implies $P\ne NP$. So, any hardness of approximation result assuming $P\ne NP$ would also follow from $NP\ne coNP$ assumption.</p>

CC BY-SA 2.5
2010-10-20T05:07:35.440Z
It is possible that NP=coNP and still P vs NP question is open. I am looking for hardness of approximation result which will become false if NP=coNP but is unaffected (i.e., still remains as a conjecture) by P!=NP.
Shiva Kintali
CC BY-SA 2.5
2010-10-20T05:21:32.757Z
In your question, you are looking for problem A such that "it is easy to approximate $A$ within a factor $\alpha$ implies NP=coNP" which eqivalent to " If $NP\ne coNP$ then it is hard to approximate A within a factor $\alpha$". Please edit your question to reflect your comment.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-20T04:50:23.733Z
2010-10-20T04:50:23.733Z
Mohammad Al-Turkistany
<p><strong>This is not a direct answer</strong></p>

<p>k-Choosability problem is $\prod_2^P$-complete. Under the assumption that
$NP \ne coNP$, k-Choosability is strictly harder than k-Coloring on general graphs. Therefore, approximating list chromatic number is strictly harder than the chromatic number. It is known that k-coloring is trivial for bipartite graphs. However, determining the list chromatic number of bipartite graphs is $NP$-hard. (even 3-Chooseability is $\prod_2^P$-complete)</p>

<p><a href="http://www.tau.ac.il/~nogaa/PDFS/british2.pdf" rel="nofollow">Noga Alon, Restricted colorings of graphs</a>
<a href="http://www.tau.ac.il/~nogaa/PDFS/british2.pdf" rel="nofollow"></a></p>

CC BY-SA 2.5
2010-10-22T20:17:24.190Z
2010-10-22T20:50:16.847Z
2010-10-22T20:50:16.847Z
Mohammad Al-Turkistany
<p>Here's a straightforward observation. If you assume $NP \neq coNP$, then it is pretty easy to see there are $NP$ optimization problems which do not even have good <em>nondeterministic</em> approximation algorithms, in some sense.</p>

<p>For example, the PCP theorem says that you can translate SAT into the problem of distinguishing whether $1-\varepsilon$ of the clauses are satisfied and all of the clauses are satisfied, for some $\varepsilon > 0$. Suppose there is a nondeterministic algorithm which can distinguish between these two cases, in the sense that the nondeterministic algorithm can report in each computation path either "all satisfied" or "at most $1-\varepsilon$", and it says "at most $1-\varepsilon$" in some path if at most $1-\varepsilon$ can be satisfied, otherwise it says "all satisfied" in every computation path if all equations can be satisfied. This is enough to decide SAT in $coNP$, so $NP=coNP$. It seems clear that the existence of such a nondeterministic algorithm has no bearing on whether $P = NP$.</p>

<p>It's quite plausible that a more "natural" scenario exists: an optimization problem which is hard to approximate in <em>deterministic</em> polynomial time under $NP \neq coNP$ but not known to be hard under $P \neq NP$. (This is probably what you really wanted to ask.) Many hardness of approximation results are first proven under some stronger assumption (e.g. $NP$ not in subexponential time, or $NP$ not in $BPP$). In some cases, later improvements weaken the necessary assumption, sometimes down to $P \neq NP$. So there is hope that there's a slightly more satisfactory answer to your question than this one. It is hard to wonder how there could be a problem that <em>cannot</em> be proved hard to approximate in deterministic polytime under $P \neq NP$, but it <em>can</em> be proved hard under $NP \neq coNP$. That would mean that $NP \neq coNP$ tells us something about deterministic computations that $P \neq NP$ doesn't already say; intuitively, this is hard to grasp.</p>

CC BY-SA 2.5
2010-10-20T10:36:48.883Z
Yes. It is hard to grasp that such hardness results are even possible. I was wondering if we can prove the non-existence of such hardness results. Phew.... it's getting complicated.
Shiva Kintali
CC BY-SA 2.5
2010-10-20T11:04:44.090Z
(1) I am afraid that you are writing the yes-case and the no-case oppositely in the second paragraph.  It is easy to construct a nondeterministic algorithm which does what you stated (reports “all satisfied” in at least one path if the formula is satisfiable and reports “at most 1−ε” in all paths if the formula is ε-far from satisfiable) by just testing all truth assignments nondeterministically.  (2) I agree about the “hard to grasp” part.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-20T10:18:45.290Z
2010-10-20T17:09:46.120Z
2010-10-20T17:09:46.120Z
Ryan Williams
<p>Two of the common assumptions for proving hardness of approximation results are $P \neq NP$ and Unique Games Conjecture. Are there any hardness of approximation results assuming $NP \neq coNP$ ? I am looking for problem $A$ such that "it is hard to approximate $A$ within a factor $\alpha$ unless $NP = coNP$".</p>

<p>It is known that "showing factor $n$ NP-hardness for shortest vector problem would imply that $NP = coNP$". Note that this is the "opposite" of what I am looking for.</p>

<p>Clarification : It is possible that $NP=coNP$ and still the P vs NP question is open. I am looking for hardness of approximation result which will become false if $NP=coNP$ but is unaffected (i.e., still remains as a conjecture) by $P \neq NP$.</p>

CC BY-SA 2.5
2010-10-20T06:11:09.523Z
@Kintali,The SVP result is interesting. Are you aware of other examples similar to the shortest vector problem result?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-21T06:59:35.910Z
I am not aware of more such results.
Shiva Kintali
<approximation-hardness><conditional-results>
Hardness of approximation assuming NP != coNP
Shiva Kintali
# Hardness of approximation assuming NP != coNP

(Asked by: username_0 on 2010-10-20)

Two of the common assumptions for proving hardness of approximation results are $P \neq NP$ and Unique Games Conjecture. Are there any hardness of approximation results assuming $NP \neq coNP$ ? I am looking for problem $A$ such that "it is hard to approximate $A$ within a factor $\alpha$ unless $NP = coNP$".

It is known that "showing factor $n$ NP-hardness for shortest vector problem would imply that $NP = coNP$". Note that this is the "opposite" of what I am looking for.

Clarification : It is possible that $NP=coNP$ and still the P vs NP question is open. I am looking for hardness of approximation result which will become false if $NP=coNP$ but is unaffected (i.e., still remains as a conjecture) by $P \neq NP$.

**Tags:** approximation-hardness, conditional-results

> **Comments:**
> **username_1**: @Kintali,The SVP result is interesting. Are you aware of other examples similar to the shortest vector problem result?  
> **username_0**: I am not aware of more such results.  

---

## 4 answers

### Answer by username_4 on 2010-10-20. Score: 20 | Accepted answer

Here's a straightforward observation. If you assume $NP \neq coNP$, then it is pretty easy to see there are $NP$ optimization problems which do not even have good *nondeterministic* approximation algorithms, in some sense.

For example, the PCP theorem says that you can translate SAT into the problem of distinguishing whether $1-\varepsilon$ of the clauses are satisfied and all of the clauses are satisfied, for some $\varepsilon > 0$. Suppose there is a nondeterministic algorithm which can distinguish between these two cases, in the sense that the nondeterministic algorithm can report in each computation path either "all satisfied" or "at most $1-\varepsilon$", and it says "at most $1-\varepsilon$" in some path if at most $1-\varepsilon$ can be satisfied, otherwise it says "all satisfied" in every computation path if all equations can be satisfied. This is enough to decide SAT in $coNP$, so $NP=coNP$. It seems clear that the existence of such a nondeterministic algorithm has no bearing on whether $P = NP$.

It's quite plausible that a more "natural" scenario exists: an optimization problem which is hard to approximate in *deterministic* polynomial time under $NP \neq coNP$ but not known to be hard under $P \neq NP$. (This is probably what you really wanted to ask.) Many hardness of approximation results are first proven under some stronger assumption (e.g. $NP$ not in subexponential time, or $NP$ not in $BPP$). In some cases, later improvements weaken the necessary assumption, sometimes down to $P \neq NP$. So there is hope that there's a slightly more satisfactory answer to your question than this one. It is hard to wonder how there could be a problem that *cannot* be proved hard to approximate in deterministic polytime under $P \neq NP$, but it *can* be proved hard under $NP \neq coNP$. That would mean that $NP \neq coNP$ tells us something about deterministic computations that $P \neq NP$ doesn't already say; intuitively, this is hard to grasp.

> **Comments:**
> **username_0**: Yes. It is hard to grasp that such hardness results are even possible. I was wondering if we can prove the non-existence of such hardness results. Phew.... it's getting complicated.  
> **username_5**: (1) I am afraid that you are writing the yes-case and the no-case oppositely in the second paragraph.  It is easy to construct a nondeterministic algorithm which does what you stated (reports “all satisfied” in at least one path if the formula is satisfiable and reports “at most 1−ε” in all paths if the formula is ε-far from satisfiable) by just testing all truth assignments nondeterministically.  (2) I agree about the “hard to grasp” part.  

---

### Answer by username_2 on 2010-10-20. Score: 8

Disclaimer: this is not a direct answer.

Actually there are many more hardness conditions other than P != NP and the UGC. David Johnson [wrote a beautiful column](http://davidsjohnson.net/columns/col25.pdf) for the Transactions on Algorithms back in 2006 on precisely this issue. He lists out the numerous different assumptions that are used to show hardness, and how they relate to each other.

Unfortunately, these are all NP vs deterministic classes (with the exception of NP and co-AM). NP vs co-NP is not covered at all.

> **Comments:**
> **username_3**: As an interesting aside, David Johnson DOES talk about NP vs co-NP in the very next column -- [NP-completeness column number 26](http://www2.research.att.com/~dsj/columns/col26.pdf)!  
> **username_2**: ah of course. I should have remembered. But no approximations though...  

---

### Answer by username_1 on 2010-10-20. Score: 4

$NP \ne coNP$ is a stronger hypothesis than $P \ne NP$ since $NP\ne coNP$ implies $P\ne NP$. So, any hardness of approximation result assuming $P\ne NP$ would also follow from $NP\ne coNP$ assumption.

> **Comments:**
> **username_0**: It is possible that NP=coNP and still P vs NP question is open. I am looking for hardness of approximation result which will become false if NP=coNP but is unaffected (i.e., still remains as a conjecture) by P!=NP.  
> **username_1**: In your question, you are looking for problem A such that "it is easy to approximate $A$ within a factor $\alpha$ implies NP=coNP" which eqivalent to " If $NP\ne coNP$ then it is hard to approximate A within a factor $\alpha$". Please edit your question to reflect your comment.  

---

### Answer by username_1 on 2010-10-22. Score: 0

**This is not a direct answer**

k-Choosability problem is $\prod\_2^P$-complete. Under the assumption that
$NP \ne coNP$, k-Choosability is strictly harder than k-Coloring on general graphs. Therefore, approximating list chromatic number is strictly harder than the chromatic number. It is known that k-coloring is trivial for bipartite graphs. However, determining the list chromatic number of bipartite graphs is $NP$-hard. (even 3-Chooseability is $\prod\_2^P$-complete)

[Noga Alon, Restricted colorings of graphs](http://www.tau.ac.il/~nogaa/PDFS/british2.pdf)


---

