Me ha fascinado la explosión extraordinaria en Smoothed Analysis y me llamó la atención una afirmación en el artículo Smoothed Analysis of Integer Programming . Esto indicó que la programación lineal entera está en P suavizado si está polinómicamente limitada. ¡Esto era esencial porque la programación de enteros es pseudo-polinomial!
La pregunta por lo tanto es:
¿Esto se traslada a otros problemas universalmente? En particular, ¿cuáles son las limitaciones?
cc.complexity-theory
smoothed-analysis
Zelah 02
fuente
fuente
Respuestas:
La programación de enteros es fuertemente NP-hard, por lo tanto, los programas de enteros en general no pueden resolverse en tiempo pseudo-polinomial. El resultado de Röglin y Vöcking es que, siempre que el rango de enteros que las variables pueden asumir esté limitado polinomialmente, la solubilidad pseudo-polinomial (aleatorizada) es equivalente a la complejidad suavizada polinómica. Por lo tanto, los programas enteros generales no tienen complejidad polinómica suavizada.
La afirmación "complejidad pseudo-polinomial aleatoria = complejidad suavizada polinomial" no se conoce en general. Por ejemplo, la heurística de volteo para Max-Cut se ejecuta en tiempo pseudo-polinomial, pero se desconoce si se puede encontrar un wrt óptimo local, la heurística de volteo con complejidad suavizada polinomial (cf. Etscheid y Röglin, SODA 2014).
fuente