¿Por qué los problemas de NP completo no tienen proporciones de aproximación similares?

Dado que 2 problemas completos de NP son, por definición, reducibles entre sí, por lo que se puede obtener una solución a uno de ellos mediante el uso de una caja negra que resuelve el otro, ¿por qué no tienen relaciones de aproximación similares (refiriéndose a sus contrapartes de optimización )? Supongo que podría entenderse una deriva constante o incluso polinómica, pero tenemos el caso de algoritmos de aproximación de factor constante para algunos problemas de NP completo y, por otro lado, otros problemas que ni siquiera pueden ser aproximados por un algoritmo de aproximación de relación polinómica , como el TSP general? Gracias

cc.complexity-theory approximation-algorithms reductions N27
fuente

porque las reducciones de recuadro negro solo conservan el aspecto SÍ / NO de los problemas (de decisión), no la cercanía de las aproximaciones.

Suresh Venkat

si reduzco 3SAT a la cubierta de vértice, entonces la cubierta de vértice de tamaño k implica satisfacción y viceversa. Pero si obtengo una cubierta de vértice de tamaño 2k, no significa que pueda satisfacer la mitad de las cláusulas.

Suresh Venkat

Elija una reducción específica de un problema de NP completo a otro e intente extenderlo para preservar las relaciones de aproximación. Verás lo que sale mal.

Peter Shor

La respuesta de Peter es la mejor de verdad. Solo pruébalo y mira qué sucede. Creo que por escepticismo filosófico quieres decir 'Realmente no entiendo la intuición'. A veces, la mejor manera es probar algunos ejemplos y dejar que la intuición crezca.

Suresh Venkat

\log | C |

$\log |C|$

| C |

$|C|$

| C |^{2}

$|C|^2$

2^{| C |}

$2^{|C|}$

C

$C$

Jukka Suomela

Respuestas:

Las reducciones se definen con respecto a la versión de decisión de los problemas. Las relaciones de aproximación para sus versiones de optimización son una pregunta separada, que parece relacionada pero no necesariamente tiene que estarlo. Entonces, para responder a su pregunta con una pregunta, desde una perspectiva filosófica, ¿por qué debería esperar que el NPC de la clase conserve relaciones de aproximación cuando no se define con respecto a ellas en primer lugar?

Lev Reyzin
fuente

"Las reducciones se definen con respecto a la versión de decisión de los problemas". ¿Es esto cierto para, digamos, reducciones de Levin ?

MS Dousti

Tienes razón, no todas las reducciones se definen como versiones de decisión de wrt, pero podemos definir NPC solo en términos de reducciones de recuadro negro, y luego supongo que puede conducir a debates sobre cómo cambian estas clases con la reducción utilizada ... Debería haber dicho "la clase NPC está definida para problemas de decisión". No es realmente un argumento preciso, ya que incluso podríamos definir una clase de problemas de decisión cuyas versiones de optimización conservan las relaciones de aproximación, pero eso no es lo que hacemos para la clase NPC. Supongo que dada la pregunta de @ N27 es una objeción filosófica, se me permite dar una respuesta filosófica. :)

Lev Reyzin