Problemas de optimización "NP-complete"

24

Estoy un poco confundido por alguna terminología que he encontrado con respecto a la complejidad de los problemas de optimización. En una clase de algoritmos, tuve el gran problema de parsimonia descrito como NP-completo. Sin embargo, no estoy exactamente seguro de lo que significa el término NP-complete en el contexto de un problema de optimización. ¿Esto solo significa que el problema de decisión correspondiente es NP-completo? ¿Y eso significa que el problema de optimización puede ser más difícil (quizás fuera de NP)?

En particular, me preocupa el hecho de que, si bien un problema de decisión de NP completo es verificable en tiempo polinómico, una solución a un problema de optimización correspondiente no parece ser verificable en tiempo polinómico. ¿Significa eso que el problema no está realmente en NP, o la verificabilidad del tiempo polinomial es solo una característica de los problemas de decisión de NP?

Aniket Schneider
fuente
3
revisa esta pregunta
Ran G.
1
También esta pregunta: Versión de optimización de problemas de decisión .
Kaveh
1
@RanG., No estoy seguro de si este es un duplicado exacto .
Kaveh
@Kaveh tienes razón, pero la gran respuesta de uli responde completamente a esta pregunta.
Ran G.
@RanG., Puede haber más de una gran respuesta. :)
Kaveh

Respuestas:

13

Un intento de una respuesta parcial:

Los problemas de decisión ya se investigaron durante algún tiempo antes de que aparecieran los problemas de optimización , en el sentido en que se tratan desde la perspectiva de los algoritmos de aproximación.

Debe tener cuidado al trasladar los conceptos de problemas de decisión. Se puede hacer y se puede dar una noción precisa de integridad de NP para problemas de optimización. Mira esta respuesta . Por supuesto, es diferente de la integridad de NP para problemas de decisión, pero se basa en las mismas ideas (reducciones).

Si se enfrenta a un problema de optimización que no permite una verificación con una solución factible, entonces no hay mucho que pueda hacer. Es por eso que generalmente se supone que:

  • Podemos verificar eficientemente si la entrada es realmente una instancia válida de nuestro problema de optimización.
  • El tamaño de las soluciones factibles está limitado polinomialmente por el tamaño de las entradas.
  • Podemos verificar eficientemente si una solución es una solución factible de la entrada.
  • El valor de una solución se puede determinar de manera eficiente.

De lo contrario, no hay mucho que podamos esperar lograr.

NPNPNP

Si desea verificar que una solución no solo es factible, sino también óptima, diría que esto es tan difícil como resolver el problema de optimización original porque, para refutar una solución factible y posiblemente óptima dada como no óptima, tiene que dar una mejor solución, lo que puede requerir que encuentre la verdadera solución óptima.

Pero eso no significa que el problema de optimización sea más difícil. Vea esta respuesta , que depende, por supuesto, de las definiciones precisas.

uli
fuente
¿Puede dar un artículo o una referencia de libro, donde pueda encontrar más información sobre una definición precisa, reducción, etc., para la dureza NP para problemas de optimización? Hasta ahora, no pude entender uno. Eso sería muy interesante para mí. Gracias.
John Threepwood
-1

La razón por la cual la mayoría de los problemas de optimización se pueden clasificar como P, NP, NP-completo, etc., son las condiciones de Kuhn-Tucker. Hablaré en términos de problemas de programación lineal, pero el KTC se aplica en muchos otros problemas de optimización. Para cada problema de optimización hay un doble. Si el objetivo en el problema original es maximizar alguna función, entonces el dual (generalmente) tiene una función que debe minimizarse. * Soluciones viables, pero no óptimas para el problema original serán inviables / inválidas para el problema dual, y viceversa. -versa. Si, y solo si, una solución es factible para el primario y el dual, es una solución óptima para ambos. (Técnicamente, puede ser una de una gran cantidad de soluciones óptimas que dan el mismo resultado).

Por lo tanto, encontrar una solución óptima para un problema de optimización es equivalente a encontrar una solución válida para el primario y el dual. Puede usar algoritmos de optimización para encontrar esa solución, pero el proceso general es una prueba de existencia.

  • Si desea pasar de la minimización a la maximización, multiplique la función objetivo por -1.
Robert I. Eachus
fuente
3
No veo cómo las condiciones KKT se relacionan con la dureza NP, ¿podría explicarlo más?
Lagarto discreto
2
Realmente no veo cómo esto responde la pregunta. P , NP , etc., son clases de problemas de decisión. Los problemas de optimización no son problemas de decisión, por lo que no están en ninguna de esas clases por definición .
David Richerby
2
Tampoco veo cómo esto responde la pregunta: este es un comentario interesante, pero parece responder a una pregunta diferente a la que se hizo. La pregunta pregunta qué significa decir que un problema de optimización es NP completo y si se puede decir que los problemas de optimización están en NP, dado que no son un problema de decisión. Esto describe cómo, dado un problema de optimización (donde las soluciones no son verificables), a menudo podemos construir un problema correspondiente donde las soluciones pueden ser verificadas. Cosas muy interesantes, pero no estoy seguro de que responda la pregunta que se hizo.
DW
1
@DW La razón principal por la que creo que esto realmente no responde a la pregunta es que, además de lo que ya se mencionó, KKT limita la configuración a la optimización matemática de funciones 'regulares' (por ejemplo, continuas, diferenciables, convexas). Esta configuración no es aplicable a la mayoría de los problemas NP-hard.
Lagarto discreto