La dureté APX n'implique aucun QPTAS?

Donc, une recherche rapide sur le Web m'a amené à croire que "APXHardness implique qu'aucun QPTAS n'existe pour un problème à moins que [une certaine classe de complexité] ne soit incluse dans une [autre classe de complexité]" et c'est bien connu aussi! Il semble que tout le monde le sait, sauf moi. Malheureusement, aucune référence à l'appui de cette déclaration n'est donnée. J'ai deux questions:

Quelle est la version la plus forte de cette déclaration actuellement connue?
Une référence? S'il vous plaît?

Merci d'avance.

La réponse de Chandra Chekuri suggère qu'une pour un problème implique -hard . Quelqu'un peut-il expliquer pourquoi c'est vrai, ou de préférence donner une référence pour cela? En d'autres termes, pourquoi l'approximation temporelle quasi polynomiale implique-t-elle la solvabilité temporelle QP? $QPTAS$ $APX$ $NP\subseteq QP$

cc.complexity-theory reference-request Sariel Har-Peled
la source

Les réponses à cette question: cstheory.stackexchange.com/questions/9350/… montrent qu'il est hautement improbable que MAX 3SAT admette quoi que ce soit de mieux que 7/8 en temps sous-exponentiel (peu probable conditionné par l'ETH).

Suresh Venkat

Réponses:

$\delta > 0$ $(1+\delta)$ $P=NP$ $P \neq NP$

$\delta > 0$ $(1+\delta)$ $\delta > 0$ $(1+\delta)$ $n^{O(\log n)}$ $n^{O(\log n)}$

Chandra Chekuri
la source

Pourquoi (PTAS

⟹

$\implies$ P = NP) moyenne (QPTAS

⟹ N P \subseteq Q P

$\implies NP\subseteq QP$

N P \subseteq Q P

$NP\subseteq QP$

@chandra Yeh. C'est crédible, ref? (Sauf à passer explicitement en revue les détails de la dureté d'approximation pour 3SAT et ainsi de suite, ce qui n'est pas difficile, mais une référence serait mieux ...)

Sariel Har-Peled

n^{O (\log n)} 2^{1 / δ}

$n^{O(\log n)}2^{1/\delta}$

δ = 1 / n

$\delta = 1/n$

@SureshVenkat Vous devez utiliser le théorème PCP qui dit que faire mieux qu'une approximation 7/8 de 3SAT est NPHard. C'est pourquoi je veux une référence;).

Sariel Har-Peled

δ

$\delta$

δ

$\delta$

P

$P$

(1 + δ)

$(1+\delta)$

P

$P$

ϵ

$\epsilon$

ϵ = δ

$\epsilon = \delta$