A dureza APX não implica QPTAS?

Portanto, uma rápida pesquisa na web me levou a acreditar que "o APXHardness implica que não existe QPTAS para um problema, a menos que [alguma classe de complexidade] esteja incluída em alguma [outra classe de complexidade]" e também é bem conhecido! Parece que todo mundo sabe disso, exceto eu. Infelizmente, nenhuma referência para apoiar esta declaração é dada. Eu tenho duas perguntas:

• Qual é a versão mais forte desta declaração atualmente conhecida?

• Uma referência? Por favor?

Desde já, obrigado.

A resposta de Chandra Chekuri sugere que um para um problema de implica . Alguém pode explicar por que é verdade ou, de preferência, dar uma referência para isso? Em outras palavras, por que a aproximação do tempo quase polinomial implica em solvabilidade no tempo de QP?A P X N P ⊆ Q $QPTAS$$APX$$NP\subseteq QP$

APX-Dureza implica que existe um de tal modo que o problema não admitir um ( 1 + δ ) -approximation a menos que P = N P . Claramente, isso exclui um PTAS (assumindo P ≠ N P ). Quanto ao QPTAS, isso será descartado, a menos que você acredite que o NP esteja contido em tempo quase polinomial. Até onde eu sei, essa é a única razão pela qual o APX-Hardness exclui um QPTAS.$\delta > 0$$(1+\delta)$$P=NP$$P \neq NP$

Como algumas pessoas perguntaram mais detalhes, aqui estão mais algumas. A dureza APX para um problema de minimização P implica em uma fixa e uma redução no tempo polinomial de 3-SAT para P, de modo que uma aproximação ( 1 + δ ) para P permita decidir se o 3-SAT fórmula é satisfatória ou não. Se existe um QPTAS para P, podemos obter, para qualquer aproximação δ > 0 a ( 1 + δ ) no tempo, digamos n O ( log n ) . Mas isso implica que podemos decidir se uma fórmula 3-SAT é satisfatória em $\delta > 0$$(1+\delta)$$\delta > 0$$(1+\delta)$$n^{O(\log n)}$ tempo que, por sua vez, implica que NP está em QP.$n^{O(\log n)}$