¿Por qué los problemas NP-completos son tan diferentes en términos de su aproximación?

Me gustaría comenzar la pregunta diciendo que soy programador y que no tengo muchos antecedentes en teoría de la complejidad.

Una cosa que he notado es que si bien muchos problemas son NP completos, cuando se extienden a problemas de optimización, algunos son mucho más difíciles de aproximar que otros.

Un buen ejemplo es TSP. Aunque todos los tipos de TSP son NP completos, los problemas de optimización correspondientes se vuelven cada vez más fáciles de aproximar con simplificaciones sucesivas. El caso general es NPO completo, el caso métrico es APX completo y el caso euclidiano en realidad tiene un PTAS.

Esto me parece contrario a la intuición, y me pregunto si hay una razón para esto.

Una razón por la que vemos diferentes complejidades de aproximación para los problemas de NP completo es que las condiciones necesarias para NP completo constituyen una medida de grano muy grueso de la complejidad de un problema. Puede estar familiarizado con la definición básica de un problema ser NP-completo:$\Pi$

1. está en NP, y$\Pi$
2. Para cualquier otro problema en NP, podemos convertir una instancia x de Ξ en una instancia y de Π en tiempo polinómico, de modo que y sea ​​una instancia sí de Π si y solo si x es una instancia sí de Ξ .$\Xi$$x$$\Xi$$y$$\Pi$$y$$\Pi$$x$$\Xi$

Considere la condición 2: todo lo que se requiere es que podamos tomar y convertirlo en algo y que conserve la respuesta sí / no de "bit único". No hay condiciones sobre, por ejemplo, el tamaño relativo de los testigos para el sí o el no (es decir, el tamaño de la solución en el contexto de optimización). Entonces, la única medida que se usa es el tamaño total de la entrada que solo da una condición muy débil en el tamaño de la solución. Entonces es bastante "fácil" convertir un Ξ en un Π .$x$$y$$\Xi$$\Pi$

Podemos ver la diferencia en varios problemas de NP completo al observar la complejidad de algunos algoritmos simples. -Coloring tiene una fuerza bruta O ( k n ) (donde n es el tamaño de entrada). Para k -Dominating Set, un enfoque de fuerza bruta toma O ( n k ) . Estos son, en esencia, los mejores algoritmos exactos que tenemos. k -Vertex Cover sin embargo tiene una O muy simple ( 2 k n c$k$$O(k^{n})$$n$$k$$O(n^{k})$$k$$O(2^{k}n^{c})$algoritmo (elija una arista, ramifique en qué punto final incluir, marque todo cubierto, continúe hasta que no tenga aristas sin marcar o alcance su presupuesto de y bactrack). Bajo reducciones polinomiales de tiempo múltiple (reducciones de Karp, es decir, lo que estamos haciendo en la condición 2 anterior), estos problemas son equivalentes.$k$

Cuando comenzamos a abordar la complejidad con herramientas incluso un poco más delicadas (complejidad de aproximación, complejidad parametrizada, cualquier otra que no se me ocurra), las reducciones que utilizamos se vuelven más estrictas, o más bien, más sensibles a la estructura de la solución, y las diferencias comienzan a aparecer; -Vertex Cover (como mencionó Yuval) tiene una aproximación simple de 2 (pero no tiene un FPTAS a menos que algunas clases de complejidad colapsen), k -Dominating Set tiene un algoritmo de aproximación ( 1 + log n ) (pero no ( c log n ) -aproximación para algunos c > $k$$k$$(1+\log n)$$(c\log n)$$c>0$), y la aproximación realmente no tiene ningún sentido para la versión sencilla de -Coloring.$k$

$O(\log n)$$1/2 + k/n$$k$$O(1)$ algoritmo de aproximación

Estos ejemplos no están completamente inventados. Los problemas de MAX-INDEPENDENT-SET (equivalente a MAX-CLIQUE) y MIN-VERTEX-COVER están estrechamente relacionados: el complemento de un conjunto independiente es una cubierta de vértice. Pero mientras que el primero es difícil de aproximar, el segundo tiene una aproximación simple de 2.

Las reducciones que muestran la dureza NP de un problema dado a veces se pueden usar para mostrar también la dureza de aproximación, pero este no es siempre el caso, depende de la reducción. Por ejemplo, la reducción de MAX-INDEPENDENT-SET a MIN-VERTEX-COVER no implica dureza de aproximación del último problema, que es mucho más fácil de aproximar que el primero.

En resumen, la dureza NP es solo un aspecto de un problema. La dureza de la aproximación es un aspecto diferente, y depende en gran medida de la noción de aproximación.

Como un enfoque intuitivo, considere que las instancias de problemas NP-completos no siempre son tan difíciles como el caso general. La satisfacción binaria (SAT) es NP-completa, pero es trivial encontrar la solución para A v B v C v D v ... Los algoritmos de complejidad solo vinculan el peor de los casos, no el caso promedio, o incluso el caso del 90% .

La forma más fácil de reducir un problema de NP completo a algo más simple es simplemente excluir las partes duras. Es trampa, sí. Pero a menudo las partes restantes siguen siendo útiles para resolver problemas del mundo real. En algunos casos, la línea entre "fácil" y "difícil" es fácil de trazar. Como señaló para TSP, hay una fuerte reducción en la dificultad al restringir el problema en torno a direcciones "normales" en las que uno podría pensar. Para otros problemas , es más difícil encontrar formas útiles de la vida real para segregar las partes fáciles y difíciles.

Para abandonar por completo el ámbito de la informática y las matemáticas, considere un automóvil viejo. Tu amigo quiere conducirlo. Si tiene que decirle, "oye, el auto funciona perfecto. Simplemente no lo tome por encima de 95 mph. Hay un bamboleo desagradable que lo dejará fuera de la carretera", probablemente no sea gran cosa. Tu amigo probablemente solo quería llevarlo por la ciudad de todos modos. Sin embargo, si tiene que decirle: "tiene que poner el embrague justo para ir del 1 ° al 2 °, o el motor se parará", podría ser más difícil para su amigo usar el automóvil por la ciudad sin algún entrenamiento menor.

Del mismo modo, si un problema de NP completo solo se vuelve difícil en casos exóticos, reduce la complejidad bastante rápido cuando se miran los subdominios. Sin embargo, si se vuelve difícil en los casos comunes, no hay tantos subdominios útiles que eviten la parte difícil.