Problemas de optimización más difíciles en Carolina del Norte

8

Cuando aprendemos problemas de optimización, generalmente consideramos la programación lineal (o más generalmente: optimización convexa) como el ejemplo más simple. Es solucionable en tiempo polinómico y tiene algoritmos relativamente fáciles de entender. Sin embargo, la versión de decisión de LP es -complete. Esto sugiere que es uno de los problemas más difíciles que podemos resolver en el tiempo polinómico. $\mathsf{P}$

Bajo el supuesto de que . ¿Cuál es el tipo de problemas de optimización natural "más difícil" con problemas de decisión en ? $\mathsf{NC} \neq \mathsf{P}$ $\mathsf{NC}$

Si esto es demasiado vago, podemos restringirlo a restricciones. ¿Cuál es el conjunto mínimo de restricciones que debemos colocar en los programas lineales (o más generalmente: programas convexos) para permitir que el problema de decisión asociado con los programas restringidos pueda resolverse en ? $\mathsf{NC}$

Motivación

En gran medida, esto es curiosidad ociosa. Sin embargo, fue provocado por " En la Unión Soviética, el problema de optimización lo resuelve" de Cosma Shalizi . En particular, si LP es demasiado difícil de resolver para tener una economía centralizada (es decir, optimizar en es pedir demasiado), entonces cualquier sistema descentralizado debe estar haciendo algún tipo de procesamiento en paralelo más rápido que el tiempo múltiple (para mí : ). $\mathsf{P}$ $\mathsf{NC}$

cc.complexity-theory optimization linear-programming Artem Kaznatcheev
fuente

Debido a que NC es una jerarquía, es poco probable que encuentre un problema "más difícil" en NC (más precisamente: NC no tiene problemas completos a menos que la jerarquía de NC colapse). Del mismo modo, probablemente no haya un conjunto mínimo de restricciones "universales" sobre LP para ponerlo en NC, aunque esto parece más difícil de descartar, incluso condicionado por supuestos naturales. (Esto no es para restarle importancia a la pregunta; me gusta la pregunta, y obviamente produjo algunas respuestas interesantes, solo una observación)

Joshua Grochow,

9

¿Conoces el trabajo en LP / SDP positivos? Hay un montón de resultados en el área, principalmente en la línea de "si las restricciones de LP / SDP son positivas, entonces el problema puede resolverse en Carolina del Norte".

Algunas referencias importantes en esta línea de trabajo son Luby-Nisan 93 y Jain-Yao 11 . Otro recurso excelente es esta diapositiva de la charla de Rahul Jain en la conferencia "Progreso reciente en algoritmos cuánticos" en IQC. Toda la charla está disponible en youtube.

Robin Kothari
fuente

1

Más precisamente, la programación lineal positiva y la programación semidefinida positiva son problemas de optimización que no solo se pueden resolver exactamente en el tiempo polinómico (es decir, están en ), sino que también admiten esquemas de aproximación . No se pueden resolver exactamente en (es decir, en ) a menos que .

P O

$\mathsf{PO}$

N C

$\mathsf{NC}$

N C

$\mathsf{NC}$

N C O

$\mathsf{NCO}$

P = N C

$\mathsf{P} = \mathsf{NC}$

argentpepper

@argentpepper, ¿dónde se hace referencia a que SDP positivo y LP es -completo?

P

$P$

T ....

2

No estoy seguro, pero es posible que le interese, si no, le pido disculpas, por el siguiente documento , que no está relacionado con un tipo natural de problema de optimización, sino que trata un problema que puede reducirse a un problema de optimización particular , cuya solución está en NC.

Igor Averbakh, Oded Berman, "Algoritmos NC paralelos para problemas de ubicación de múltiples instalaciones con comunicación mutua y sus aplicaciones", Redes, Volumen 40, Número 1, páginas 1–12, agosto de 2002, Wiley

DOI: 10.1002 / net.10027

Resumen

El problema genérico estudiado es ubicar p instalaciones distinguibles en un árbol para satisfacer las restricciones de límite superior en las distancias entre pares de instalaciones, dado que cada instalación debe ubicarse dentro de su propia región factible, que se define como un subárbol del árbol. Presentamos un esquema de ubicación paralela (PLS) para resolver el problema que se puede implementar como un algoritmo NC. También presentamos algoritmos NC paralelos basados en el PLS para las versiones minimax del problema, incluido el problema del centro p con restricción de distancia con comunicación mutua. Combinando el PLS y la técnica paramétrica mejorada de Megiddo, desarrollamos algoritmos en serie fuertemente polinómicos para los problemas de minimax; Los algoritmos tienen las mejores complejidades disponibles actualmente en la literatura.

Massimo Cafaro
fuente

Problemas de optimización más difíciles en Carolina del Norte

Motivación

Respuestas: