12
$\begingroup$

So, a quick search on the web led me to believe that "APXHardness implies that no QPTAS exist for a problem unless [some complexity class] is included in some [other complexity class]" and it is well known too! It seems like everybody knows this except for me. Unfortunately, no reference to support this statement is given. I have two questions:

  • What is the strongest version of this statement that is currently known?

  • A reference? Please?

Thanks in advance.

Chandra Chekuri's answer suggests that a $QPTAS$ for a $APX$-hard problem implies $NP\subseteq QP$. Can anyone explain why it is true, or preferably give a reference for that? In other words, why does quasi polynomial time approximability imply QP time solvability?

Improve this question
$\endgroup$
1
11
$\begingroup$

APX-Hardness implies that there is a $\delta > 0$ such that the problem does not admit a $(1+\delta)$-approximation unless $P=NP$. Clearly this rules out a PTAS (assuming $P \neq NP$). As for QPTAS, it will rule it out unless you believe that NP is contained in quasi-polynomial time. As far as I know, that is the only reason why APX-Hardness rules out a QPTAS.

Since a couple of people asked more details, here are some more. APX-Hardness for a minimization problem P implies that there is a fixed $\delta > 0$ and a polynomial-time reduction from 3-SAT to P such that a $(1+\delta)$-approximation for P allows one to decide whether the 3-SAT formula is satisfiable or not. If there is a QPTAS for P we can obtain for any fixed $\delta > 0$ a $(1+\delta)$-approximation in time say $n^{O(\log n)}$. But this implies that we can decide whether a 3-SAT formula is satisfiable in $n^{O(\log n)}$ time which in turn implies that NP is in QP.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Why does (PTAS$\implies$ P=NP) mean (QPTAS$\implies NP\subseteq QP$)? Doesn't QPTAS means approximation in quasi-polynomial time while $NP\subseteq QP$ requires exact solution? $\endgroup$ – R B Mar 23 '14 at 19:59
  • $\begingroup$ @chandra Yeh. Thats believable, ref? (Except for explicitly going through the details of hardness of approximation for 3SAT and so on, which is not hard, but a ref would be better...) $\endgroup$ – Sariel Har-Peled Mar 23 '14 at 22:54
  • $\begingroup$ @ChandraChekuri I'm almost certainly being dense here, but if your QPTAS for 3SAT ran in time $n^{O(\log n)}2^{1/\delta}$, then I don't see how I can conclude that I'd decide 3SAT in QP time (because presumably I'd need to set $\delta = 1/n$. Unless there's some amplification going on that I'm missing. $\endgroup$ – Suresh Venkat Mar 25 '14 at 3:23
  • $\begingroup$ @SureshVenkat You need to use the PCP theorem that says that doing better than 7/8 approximation to 3SAT is NPHard. That is why I want a ref ;). $\endgroup$ – Sariel Har-Peled Mar 25 '14 at 3:47
  • 2
    $\begingroup$ @SureshVenkat the QPTAS is not for 3-SAT. It is for the problem P and $\delta$ is a fixed constant. APX-Hardness for P implies that there is a fixed constant $\delta$ such that any algorithm that solves $P$ to better than $(1+\delta)$-solves 3-SAT. The dependence of the running time of the QPTAS for $P$ on $\epsilon$ could be arbitrarily bad but I am going to use it only for $\epsilon = \delta$ which is fixed. $\endgroup$ – Chandra Chekuri Mar 25 '14 at 3:52

Your Answer

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

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