12

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?

András Salamon
  • 19,000
  • 3
  • 64
  • 150
Sariel Har-Peled
  • 9,626
  • 31
  • 53
  • 2
    The answers to this question: http://cstheory.stackexchange.com/questions/9350/super-polynomial-time-approximation-algorithms-for-max-3sat show that it's highly unlikely that MAX 3SAT admits anything better than 7/8 in subexponential time (unlikely conditioned on the ETH). – Suresh Venkat Mar 24 '14 at 23:39

1 Answers1

11

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.

Chandra Chekuri
  • 6,999
  • 31
  • 39
  • 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? – R B Mar 23 '14 at 19:59
  • @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...) – Sariel Har-Peled Mar 23 '14 at 22:54
  • @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. – Suresh Venkat Mar 25 '14 at 03:23
  • @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 ;). – Sariel Har-Peled Mar 25 '14 at 03:47
  • 2
    @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. – Chandra Chekuri Mar 25 '14 at 03:52