¿La integridad de PSPACE implica dureza de aproximación?

Se menciona en un comentario en otra publicación cstheorySE que la integridad de PSPACE implica dureza APX. ¿Alguien puede explicar / compartir una referencia para ello?

¿Es esto "apretado"? (es decir, ¿hay problemas completos de PSPACE cuyo problema de optimización admite una aproximación de factor constante en el tiempo polivinílico?)

¿Qué pasa con la integridad de algún nivel de PH? ¿Implica alguna dureza de aproximación?

cc.complexity-theory approximation-algorithms approximation-hardness np pspace RB
fuente

Ver arxiv.org/pdf/math/9409225.pdf

Saeed

Este documento parece dar resultados de PTAS para problemas completos de PSPACE: cs.albany.edu/~madhav/pubs.d/stoc94.ps

Sasho Nikolov

Ugh, ese fue un mal comentario. La idea era hacer una conjetura heurística, ¡lo siento si surgió como una declaración de hecho! Uno es una clase de problemas de decisión y uno es una clase de problemas de función, por lo que la declaración ni siquiera está bien definida. Creo que el razonamiento fue que puedes responder un problema en APX exactamente usando el espacio polinomial. Pero tomaría algo de trabajo formalizar la conexión y no me refería a ningún resultado formal que conociera.

usul

f (x)

$f(x)$

\hat{f} (x) = f (x) + n k

$\hat{f}(x) = f(x) + nk$

k

$k$

f

$f$

\hat{f}

$\hat{f}$

f

$f$

(1 - ϵ)

$(1-\epsilon)$

(1 - 1 / n)

$(1-1/n)$ ) algoritmo de aproximación cuando hay una solución factible. Este argumento debería ser válido incluso para las clases "más difícil" que PSPACE-complete.

Yonatan N

\subseteq

$\subseteq$

Respuestas:

Como todavía no hay respuesta, giro mi comentario para responder, Marathe et al. en su artículo ICALP93 , definieron algunos problemas que están completos en PSPACE pero admiten aproximaciones de factores constantes, también proporcionan algunos resultados de inaproximabilidad. Para esta pregunta en particular, considere MAX3SAT, el problema de decisión correspondiente está completo para PSPACE incluso si el gráfico SAT correspondiente tiene una estructura jerárquica como se definieron en su documento, pero este problema tiene un algoritmo de garantía de aproximación 2 en estructura jerárquica.

Saeed
fuente