¿Es una regla que los problemas discretos son NP-hard y los problemas continuos no lo son?

En mi educación en ciencias de la computación, noto cada vez más que la mayoría de los problemas discretos son NP completos (al menos), mientras que la optimización de problemas continuos es casi siempre fácil de lograr, generalmente a través de técnicas de gradiente. ¿Hay excepciones a esto?

Un ejemplo que me encanta es el problema donde, dado distinto , deciden si: ∫ π - π cos ( a 1 z ) cos ( a 2 z ) ... cos ( a n z $a_1, a_2, \ldots, a_n \in \mathbb{N}$

Al principio, esto parece un problema continuo para evaluar esta integral, sin embargo, es fácil demostrar que esta integral no es cero si existe una partición equilibrada del conjunto , por lo que este problema integral es en realidad NP-completo.$\{a_1, \ldots, a_n\}$

Por supuesto, animo a jugar con algunas herramientas numéricas para convencerse de que la mayoría (si no todos) los trucos numéricos para evaluar esta integral están condenados al fracaso una vez que sea ​​lo suficientemente grande.$n$

Hay muchos problemas continuos de la forma "prueba si esta entrada combinatoria puede realizarse como una estructura geométrica" ​​que están completos para la teoría existencial de los reales , un análogo continuo de NP. En particular, esto implica que estos problemas son NP-hard en lugar de polinomialmente solucionables. Los ejemplos incluyen probar si un gráfico dado es un gráfico de distancia unitaria, si un gráfico dado se puede dibujar en el plano con bordes de segmento de línea recta y como máximo un número dado de cruces, o si una disposición de pseudolina dada se puede estirar para formar una línea arreglo.

Hay otros problemas continuos que son aún más difíciles: por ejemplo, encontrar un camino más corto entre los obstáculos poliédricos en 3D es completo para PSPACE (Canny & Reif, FOCS'87).

Si bien esto no responde exactamente a su pregunta original, es un ejemplo (conjetural) de una especie de contrapunto filosófico: un problema donde la presentación es discreta pero toda la dureza proviene del aspecto 'continuo' del problema.

El problema es el problema de la suma de las raíces cuadradas : dados dos conjuntos de enteros y B = { b 1 , b 2 , ... , b n } , es ∑ m i = 1$A=\{a_1, a_2, \ldots, a_m\}$$B=\{b_1, b_2, \ldots, b_n\}$$\sum_{i=1}^m \sqrt{a_i}\leq\sum_{j=1}^n\sqrt{b_j}$difícil, se sospecha ampliamente que puede ser NP-duro y de hecho puede estar fuera de NP (hay, como se señaló en los comentarios, excelentes razones para creer que no es NP-completo); la única contención conocida hasta la fecha es varios niveles más arriba en la jerarquía polinómica. Obviamente, la presentación de este problema es lo más discreta posible (un conjunto de enteros y una pregunta de sí / no sobre ellos), pero el desafío surge porque si bien calcular las raíces cuadradas con cualquier precisión específica es un problema fácil, es posible que sea necesario calcularlas. a una precisión alta (potencialmente superpolinómica) para resolver la desigualdad de una forma u otra. Este es un problema 'discreto' que surge en un sorprendente número de contextos de optimización y ayuda a contribuir a su propia complejidad.

Los problemas discretos generalmente tienden a ser más difíciles (por ejemplo, LP frente a ILP), pero no es la discreción en sí misma el problema ... es cómo las restricciones afectan cómo puedes buscar en tu dominio. Por ejemplo, puede pensar que optimizar un polinomio es algo que puede hacer eficientemente, pero decidir la convexidad de los cuartos (polinomios de grado 4) es NP-difícil .

Lo que significa que incluso si ya tiene el óptimo de alguna manera, simplemente demostrar que está en el óptimo ya es NP-hard.

Aunque para algunos problemas populares, es cierto, creo que ambos supuestos son, dependiendo de lo que defina como un problema de optimización, no son ciertos.

Primero algunas definiciones: la mayoría de los problemas de optimización no son parte de NP . Por ejemplo, para el problema de la mochila : no se puede explotar el no determinismo para construir la bolsa más valiosa, simple porque las diferentes ramas no deterministas no tienen memoria compartida. NP también se define como "polinomialmente verificable" (verificar un certificado) [1, p. 34]. En este caso, el certificado es, por ejemplo, una bolsa : una cadena de bits en la que si se establece el i -ésimo bit, implica que el ítem i -ésimo es parte de la bolsa. De hecho, puede verificar en el tiempo polinómico si dicha bolsa es más valiosa que un umbral dado (esta es la variante de decisión), pero, hasta donde sabemos, no puede, basándose en una sola bolsa (un número polinómico de bolsas), decidir si esa bolsa es la más valiosa de todas las bolsas posibles. Esa es una diferencia vital entre, por ejemplo, NP y EXP : en EXP , puede enumerar todas las bolsas posibles y llevar la contabilidad sobre cuál es la mejor bolsa.

La variante de decisión de los problemas de optimización es en algunos casos parte de NP , uno necesita hacer una distinción clara entre el sabor de maximización y el sabor de decisión . En el sabor de la decisión, la pregunta es: " Dado un problema de optimización y un límite de utilidad, ¿existe una solución con un límite mayor o igual a ese límite de utilidad " (o ligeramente modificado para un problema de minimización).

También supongo que por NP te refieres a la parte (hipotética) de NP que no es parte de P . Si P = NP , por supuesto, NP-complete todavía existe, pero será igual a P (solo coincide con P para algunas nociones de reducción, como reducciones de tiempo múltiple polinomial por @ AndrásSalamon), lo que no es tan impresionante ( y reduciría la " brecha " que está indicando en su pregunta).

Cada vez más noto que la mayoría de los problemas discretos son NP completos.

Ahora que lo hemos resuelto: hay muchos problemas de optimización en P : problema de ruta más corta , problema de flujo máximo (para capacidades integrales), árbol de expansión mínima y coincidencia máxima . Aunque estos problemas pueden parecerle "triviales de resolver", siguen siendo problemas de optimización y, en muchos casos, la construcción (y la prueba de su corrección) no es tan fácil. Por lo tanto, el reclamo no contiene todos los problemas discretos que son NP completos. Dado que P no es igual a NP , estos problemas no pueden ser NP completos .

$\Sigma^P_i$

Mientras que la optimización de problemas continuos es casi siempre fácil de lograr.

Un problema continuo popular que es NP-hard es la programación cuadrática .

$\vec{x}$

En realidad, la programación lineal también se considera desde hace mucho tiempo NP-hard , pero con una heurística de muy buen rendimiento (el método Simplex ). Sin embargo, el algoritmo de Karmarkar está en P .

Desde el momento en que el problema de optimización se ocupa de objetos no convexos, en general será difícil, si no imposible, encontrar un algoritmo eficiente.

Bibliografía

[1] Complejidad computacional, un enfoque moderno , Sanjeev Arora y Boaz Barak