La dureza APX no implica QPTAS?

Por lo tanto, una búsqueda rápida en la web me llevó a creer que "APXHardness implica que no existe QPTAS para un problema a menos que [alguna clase de complejidad] esté incluida en alguna [otra clase de complejidad]" y ¡también es bien conocido! Parece que todo el mundo lo sabe, excepto yo. Desafortunadamente, no se da ninguna referencia para apoyar esta declaración. Tengo dos preguntas:

¿Cuál es la versión más fuerte de esta declaración que se conoce actualmente?
¿Una referencia? ¿Por favor?

Gracias por adelantado.

La respuesta de Chandra Chekuri sugiere que una para un problema -Hard implica . ¿Alguien puede explicar por qué es cierto, o preferiblemente dar una referencia para eso? En otras palabras, ¿por qué la aproximabilidad de tiempo cuasi polinomial implica la capacidad de solución de tiempo QP? $QPTAS$ $APX$ $NP\subseteq QP$

cc.complexity-theory reference-request Sariel Har-Peled
fuente

Las respuestas a esta pregunta: cstheory.stackexchange.com/questions/9350/… muestran que es muy poco probable que MAX 3SAT admita algo mejor que 7/8 en tiempo subexponencial (poco probable condicionado por el ETH).

Suresh Venkat

Respuestas:

APX-Dureza implica que existe un tal que el problema no admite un : Aproximación a menos que . Claramente esto descarta un PTAS (suponiendo ). En cuanto a QPTAS, lo descartará a menos que crea que NP está contenido en un tiempo cuasi polinomial. Que yo sepa, esa es la única razón por la cual APX-Hardness descarta un QPTAS. $\delta > 0$ $(1+\delta)$ $P=NP$ $P \neq NP$

Dado que un par de personas pidieron más detalles, aquí hay algunos más. La dureza APX para un problema de minimización P implica que hay un fijo y una reducción del tiempo polinomial de 3-SAT a P, de modo que una aproximación para P permite decidir si el 3-SAT La fórmula es satisfactoria o no. Si hay un QPTAS para P, podemos obtener cualquier aproximación a fija en el tiempo, digamos . Pero esto implica que podemos decidir si una fórmula 3-SAT es satisfactoria en $\delta > 0$ $(1+\delta)$ $\delta > 0$ $(1+\delta)$ $n^{O(\log n)}$ tiempo que a su vez implica que NP está en QP. $n^{O(\log n)}$

Chandra Chekuri
fuente

¿Por qué (PTAS

⟹

$\implies$ P = NP) media (QPTAS

)? ¿QPTAS no significa aproximación en tiempo cuasi polinomial mientras que

requiere una solución exacta?

⟹ N P \subseteq Q P

$\implies NP\subseteq QP$

N P \subseteq Q P

$NP\subseteq QP$

@chandra Yeh. Eso es creíble, ref? (Excepto por examinar explícitamente los detalles de la dureza de la aproximación para 3SAT, etc., que no es difícil, pero un árbitro sería mejor ...)

Sariel Har-Peled

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

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

δ = 1 / n

$\delta = 1/n$

@SureshVenkat Debe usar el teorema de PCP que dice que hacer una aproximación mejor que 7/8 a 3SAT es NPHard. Por eso quiero una referencia;).

Sariel Har-Peled

δ

$\delta$

δ

$\delta$

P

$P$

(1 + δ)

$(1+\delta)$

P

$P$

ϵ

$\epsilon$

ϵ = δ

$\epsilon = \delta$