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

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

CC BY-SA 3.0
2014-03-23T19:59:40.417Z
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
CC BY-SA 3.0
2014-03-23T22:54:48.327Z
@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
CC BY-SA 3.0
2014-03-25T03:23:10.200Z
@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
CC BY-SA 3.0
2014-03-25T03:47:04.827Z
@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
CC BY-SA 3.0
2014-03-25T03:52:45.220Z
@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
CC BY-SA 3.0
2014-03-23T18:21:54.083Z
2014-03-25T02:08:51.250Z
2014-03-25T02:08:51.250Z
Chandra Chekuri
<p>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:</p>

<ul>
<li><p>What is the strongest version of this statement that is currently known?</p></li>
<li><p>A reference? Please? </p></li>
</ul>

<p>Thanks in advance.</p>

<hr>

<p>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?</p>

CC BY-SA 3.0
2014-03-24T23:39:52.153Z
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
<cc.complexity-theory><reference-request>
APX Hardness implies no QPTAS?
Sariel Har-Peled
# APX Hardness implies no QPTAS?

(Asked by: username_0 on 2014-03-23)

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?

**Tags:** cc.complexity-theory, reference-request
> **Comments:**
> **username_1**: 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).  

---

## 1 answers

### Answer by username_2 on 2014-03-23. Score: 11 | Accepted answer

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.

> **Comments:**
> **username_3**: 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?  
> **username_0**: @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...)  
> **username_1**: @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.  
> **username_0**: @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 ;).  
> **username_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.  

---

