Análisis suavizado: si un problema tiene complejidad pseudopolinómica, ¿está en Smooth P?

9

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?

Zelah 02
fuente
99
¿Podría dar más detalles sobre lo que se entiende por "polinomialmente limitado" en este contexto?
András Salamon

Respuestas:

4

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).

Bodo Manthey
fuente