¿APX está contenido en NP?

15

Se dice que un problema P está en APX si existe alguna constante c> 0 tal que existe un algoritmo de aproximación de tiempo polinómico para P con factor de aproximación 1 + c.

APX contiene PTAS (visto simplemente seleccionando cualquier constante c> 0) y P.

¿APX está en NP? En particular, ¿la existencia de un algoritmo de aproximación de tiempo polinómico para algún factor de aproximación implica que el problema está en NP?

cc.complexity-theory complexity-classes apx Andrew W.
fuente
Creo que "lo que se sabe sobre la clase X en relación con todas las demás clases Y" es una pregunta demasiado vaga, a menos que se proporcionen algunos detalles adicionales sobre los tipos de relaciones buscadas.
András Salamon
Me refiero a relaciones como 'contiene', 'está contenido en', 'no contiene'.
Andrew
Después de pensarlo un poco, reduje la pregunta a la relación específica que más me interesa.
Andrew W.
1
¿Qué significa exactamente preguntar si APX está contenido en NP? APX consta de problemas aproximados de "optimización de NP" mientras que NP consiste en problemas de decisión. Además, por definición, la versión de decisión de un problema de optimización de NP está en NP. ¿Quizás tenías algo más en mente?
Joshua Grochow
Tienes razón Joshua. Ian respondió la pregunta que debería haber hecho.
Andrew W.

Respuestas:

20

APX se define como un subconjunto de NPO, entonces sí, si un problema de optimización está en APX, entonces el problema de decisión correspondiente está en NP.

Sin embargo, si lo que está preguntando es si un problema arbitrario debe estar en NP (o NPO) si hay una aproximación poli tiempo O (1), entonces la respuesta es no. No conozco ningún problema natural que sirva como contraejemplo, pero uno podría definir un problema de maximización artificial donde el objetivo es la suma de dos términos, un término grande que se optimiza fácilmente en P y un término mucho más pequeño eso agrega una pequeña cantidad si parte de la solución codifica una respuesta a algún problema difícil (fuera de NP). Entonces podría encontrar, por ejemplo, una aproximación de 2 en el tiempo polivinílico concentrándose en el término fácil, pero encontrar una solución óptima requeriría resolver el difícil problema.

Ian
fuente
2
Acepté su respuesta porque abordaba tanto la pregunta que hice ('¿El APX está contenido en NP?') Como la pregunta que debería haber hecho ('¿Un poli-tiempo O (1) implica una solución exacta en NP?').
Andrew W.
1
Una amplia gama de problemas que no están contenidos en NPO y NP pero que tienen una aproximación de factor constante es la clase de problemas en línea (La pregunta sobre qué clase de complejidad contiene problemas en línea está aquí cstheory.stackexchange.com/questions/1664/… ) .
Oleksandr Bondarenko