APX Hardness implies no QPTAS? 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?
APX-Hardness implies that there is a $\delta &gt; 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 &gt; 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 &gt; 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.