32
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ @Kintali,The SVP result is interesting. Are you aware of other examples similar to the shortest vector problem result? $\endgroup$ Oct 20, 2010 at 6:11
  • $\begingroup$ I am not aware of more such results. $\endgroup$ Oct 21, 2010 at 6:59

4 Answers 4

20
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Oct 20, 2010 at 10:36
  • $\begingroup$ (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. $\endgroup$ Oct 20, 2010 at 11:04
8
$\begingroup$

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 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.

$\endgroup$
2
  • 2
    $\begingroup$ As an interesting aside, David Johnson DOES talk about NP vs co-NP in the very next column -- NP-completeness column number 26! $\endgroup$ Oct 20, 2010 at 4:28
  • $\begingroup$ ah of course. I should have remembered. But no approximations though... $\endgroup$ Oct 20, 2010 at 4:33
4
$\begingroup$

$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.

$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$ Oct 20, 2010 at 5:07
  • $\begingroup$ 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. $\endgroup$ Oct 20, 2010 at 5:21
0
$\begingroup$

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

$\endgroup$

Your Answer

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

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