¿Son todos los problemas de programación lineal entera NP-Hard?

11

Según tengo entendido, el problema de asignación está en P ya que el algoritmo húngaro puede resolverlo en tiempo polinómico - O (n 3 ). También entiendo que el problema de asignación es un problema de programación lineal de enteros , pero la página de Wikipedia dice que esto es NP-Hard. Para mí, esto implica que el problema de asignación está en NP-Hard.

Pero seguramente el problema de asignación no puede estar tanto en P como en NP-Hard, de lo contrario, P sería igual a NP? ¿La página de Wikipedia simplemente significa que el algoritmo general para resolver todos los problemas de ILP es NP-Hard? Algunas otras fuentes afirman que ILP es NP-Hard, por lo que esto realmente confunde mi comprensión de las clases de complejidad en general.

Mate
fuente
44
NP-hard significa que (a menos que P = NP) cada algoritmo determinista polytime falla en algún conjunto (infinito) de instancias. Por lo general, también hay conjuntos de instancias fáciles.
Sasho Nikolov
1
Tenga en cuenta que la afirmación no es "cada IP es NP-hard" sino "resolver cada IP es NP-hard".
Raphael
1
Como comentario, la IP para la dimensión fija está en P.
A.Schulz

Respuestas:

20

Si un problema es NP-Hard significa que existe una clase de instancias de ese problema que son NP-Hard. Es perfectamente posible que otras clases específicas de instancias puedan resolverse en tiempo polinómico.

Considere, por ejemplo, el problema de encontrar una coloración 3 de un gráfico . Es un conocido problema NP-Hard. Ahora imagine que sus instancias están restringidas a gráficos que son, por ejemplo, árboles. Claramente, puede encontrar fácilmente una coloración 3 de un árbol en tiempo polinómico (de hecho, también puede encontrar una coloración 2).

Considere los problemas de decisión por un segundo. Un método para probar la dureza de un problema de decisión es idear una reducción polinómica (Karp) de otro problema que se sabe que es NP-Hard. En esta reducción se demuestra que existe una función que asigna cada instancia del problema a una instancia del problema tal que: es una instancia de sí a favor de es una instancia de sí para . Esto implica que resolver debe ser "al menos tan difícil" como resolver sí mismo.Q f q Q P q QPAGSQFqQPAGSqP f ( q ) qQF(q)PAGSF(q)q

Aviso cómo no se requiere para la imagen de sea igual al conjunto de las instancias de . Por lo tanto, es perfectamente posible que el problema restringido a algún subconjunto de instancias no sea difícil.P PFPAGSPAGS

Para volver a su pregunta original:

  • El problema de asignación se puede resolver en tiempo polinómico, es decir, se puede calcular una solución a cada instancia del problema de asignación en tiempo polinómico.
  • ILP es NP-Hard: en general, podría ser difícil calcular una solución a un problema de ILP, es decir, hay casos de ILP que son difíciles.
  • Algunas instancias específicas de ILP se pueden resolver en tiempo polinómico.
Steven
fuente
¿Podría explicar si es necesario que mapee cada instancia de ¿No podemos mapear un subconjunto de ? es decir, ¿la preimagen de tiene que ser todo ? Q Q f QFQQFQ
Mat
No es necesario que para asignar cada instancia de , siempre que mapea un (infinita) de clase de casos difíciles de . Por ejemplo, para mostrar que es NP-Hard, se puede proporcionar una reducción del problema de 3 coloraciones restringido a gráficos planos. Q Q PFQQPAGS
Steven
14

No, los casos especiales pueden ser más fáciles.

Considere esta IP, por ejemplo, dada unayo0 0 para yo[1 ..norte] :

minyo=1norteXyounayo

st y para .yo=1norteXyo1xiNi[1 ..n]
 Xyonorteyo[1 ..norte]

Encuentra el mínimo entre (aquello para lo cual, inevitablemente, en una solución óptima). Encontrar el mínimo de números es claramente un problema polinómico.una1,...,unanorteXyo=1norte

Rafael
fuente
0

Puede modelar un problema polinomialmente solucionable como una IP. Esto no significa que el problema sea NP-duro. Simplemente significa que no existe un algoritmo polinómico conocido para resolver el modelo IP de su problema (a menos que P = NP).

Entonces, como sugirió, el problema de asignación está en P pero su modelo de IP es NP-hard.

Austen
fuente
3
La IP en la respuesta de Rafael se puede resolver en tiempo polinómico. En otras palabras, en general no conocemos un algoritmo rápido para resolver IP, pero hay casos especiales de problemas de IP para los que tenemos algoritmos rápidos.
Juho
0

No, hay un tipo especial de programa entero, si la matriz de restricción es TUM (matriz totalmente unimodular), entonces se puede relajar en el programa lineal, que se puede resolver en tiempo polinómico.

Jianhao Ma
fuente
-4

El problema de asignación no es un ILP, sino un problema de LP y, por lo tanto, no NP-hard.

Julia
fuente
44
No estoy seguro de por qué crees que el problema de asignación no es un ILP. Sucede que, en este caso, la solución óptima para el programa lineal es también la solución óptima para el programa lineal entero ... pero eso no significa que no sea una instancia de ILP.
DW
Además, las instancias individuales por sí mismas nunca son NP-hard. Desea decir "esta es realmente una instancia fácil", pero esa es una declaración mucho más complicada (defina "fácil").
Raphael