¿Problemas que se resuelven de forma contraintuitiva en la práctica?

Recientemente, pasé por la experiencia divertida y dolorosa de explicar informalmente el concepto de complejidad computacional a un programador autodidacta joven y talentoso, que nunca antes había tomado un curso formal sobre algoritmos o complejidad. No es sorprendente que muchas nociones parecieran extrañas al principio, pero tenían sentido con algunos ejemplos (PTIME, intractabilidad, indisputabilidad) , mientras que otras parecen ser más naturales (clasificación de problemas mediante reducciones, tiempo y espacio como recursos, análisis asintótico) . Todo iba bien hasta que accidentalmente admití que SATpuede resolverse eficientemente * en la práctica ... Y así, los perdí. No importa qué tan convincente que estaba tratando de argumentar a favor de la teoría, el niño estaba convencido de que todo era artificial basura matemáticas que no debía cuidar. Bien...

¯ \ _ (ツ) _ / ¯

No, no estaba con el corazón roto, ni realmente me importaba lo que él pensara, ese no es el punto de esta pregunta. Nuestra conversación me hizo pensar en una pregunta diferente,

¿Cuánto sé realmente acerca de los problemas que son teóricamente intratables (complejidad de tiempo superpolinomial) pero prácticamente solucionables (a través de heurísticas, aproximaciones, solucionadores SAT, etc.)?

Me di cuenta, no mucho. Sé que hay algunos solucionadores SAT muy eficientes que resuelven instancias enormes de manera eficiente, que Simplex funciona muy bien en la práctica, y tal vez algunos problemas o algoritmos más. ¿Me pueden ayudar a pintar una imagen más completa? ¿Qué problemas conocidos o incluso clases de problemas están en esta categoría?

TL; DR: ¿Cuáles son los problemas que se resuelven de forma contraintuitiva en la práctica? ¿Hay un recurso (actualizado) para leer más? ¿Tenemos una caracterización para ellos? Y, finalmente, como una pregunta de discusión general, ¿no deberíamos?

EDITAR # 1: Al tratar de responder mi última pregunta de discusión sobre tal caracterización , me presentaron el análisis suavizado de algoritmos, un concepto introducido por Daniel Spielman y Shang-Hua Teng en [1] que continuamente interpola entre el peor de los casos y Análisis de casos promedio de algoritmos. No es exactamente la caracterización discutida anteriormente, pero captura el mismo concepto, y lo encontré interesante.

[1] Spielman, Daniel A. y Shang-Hua Teng. "Análisis suavizado de algoritmos: por qué el algoritmo simplex generalmente toma tiempo polinomial". Revista de la ACM (JACM) 51, no. 3 (2004): 385-463.

• Las instancias SAT altamente estructuradas (incluso en millones de variables) a menudo se pueden resolver en la práctica. Sin embargo, las instancias de SAT aleatorias cerca del umbral de satisfacción con incluso unos cientos de variables aún están abiertas (lo que significa, incluso en la práctica, si genera algo que tal vez nunca sepa en la vida del universo si lo que generó es satisfactorio o no utilizando solucionadores SAT actuales). Puede interesarle esta pregunta relacionada y sus respuestas.

• Los buscadores de camarillas también son sorprendentemente buenos "en la práctica"

  • Con respecto a los buscadores de camarillas, (parte de la) explicación se da mediante un análisis de casos promedio de los algoritmos en cuestión.

    Ver https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub

• La programación de enteros y la programación mixta de enteros lineales (con algunas variables racionales y algunas de enteros) son el foco de todos los departamentos de Investigación de Operaciones, y a menudo (pero no siempre) se pueden resolver en la práctica.

• $\mathsf{PSPACE}$$\mathsf{PSPACE}$

• $\mathsf{EXPSPACE}$

• Como ya se señaló en los comentarios de DW, el isomorfismo gráfico se puede resolver prácticamente en la práctica. Es muy difícil eliminar el software GI moderno como nauty, bliss, saucy, etc.

El sistema de tipo Hindley-Milner se utiliza en lenguajes de programación funcionales (Haskell, SML, OCaml). El algoritmo de inferencia de tipo es casi lineal en la práctica y funciona increíblemente bien, ¡pero se sabe que es DEXPTIME-complete!

Un comentario general: no es sorprendente que la peor complejidad no sea necesariamente una muy buena medida del rendimiento práctico en un algoritmo. Sin embargo, decir que la discrepancia entre la teoría y la práctica hace que la teoría de la complejidad sea inútil es como decir que los números naturales son un desperdicio porque solo usamos una cantidad minúscula de todos los números disponibles. Un famoso filósofo dijo una vez que "la experiencia sin teoría es ciega, pero la teoría sin experiencia es un mero juego intelectual".

Más ejemplos, principalmente de lenguajes de programación:

1. k-CFA (k-Control Flow Analysis) es EXPTIME-complete (Van Horn y Mairson 2008), pero los compiladores de optimización de todo el programa como MLton lo realizan de todos modos. Los tiempos de compilación son largos, pero rara vez desastrosos.
2. La resolución de sobrecarga (dinámica) generalmente es NP-completa (Palsberg 2012). Pero rara vez es un problema en el mundo real.
3. $k$
4. La resolución SMT generalmente es NP-completa, pero los solucionadores SMT comerciales (como Z3 y CVC4) suelen ser bastante efectivos. No trabajo directamente con solucionadores SMT, pero he usado Z3 indirectamente de Liquid Haskell y Dafny, y los tiempos de verificación parecen estar bien.
5. El problema de decisión para la aritmética de Presburger es realmente complejo (Fischer y Rabin 1974), pero el algoritmo de decisión de Bill Pugh, la prueba Omega (Pugh 1991), generalmente se ejecuta en un tiempo polinómico de bajo orden.

$O$$n$$n$

Referencias

[1] David Van Horn y Harry G. Mairson. 2008. La decisión de kCFA está completa por EXPTIME. En Actas de la 13ª Conferencia Internacional ACM SIGPLAN sobre Programación Funcional (ICFP '08). ACM, Nueva York, NY, EE. UU., 275-282.

[2] http://web.cs.ucla.edu/~palsberg/paper/dedicated-to-kozen12.pdf

[3] MJ Fischer y MO Rabin. 1974. COMPLEJIDAD SUPER EXPONENCIAL de la ARITMÉTICA PRESBURGER. Reporte técnico. Instituto de Tecnología de Massachusetts, Cambridge, MA, EE. UU.

[4] William Pugh. 1991. La prueba Omega: un algoritmo de programación entero rápido y práctico para el análisis de dependencia. En Actas de la Conferencia ACM / IEEE de 1991 sobre Supercomputación (Supercomputing '91). ACM, Nueva York, NY, EE. UU., 4-13.

la formación de redes neuronales utilizando métodos de descenso de gradiente también se ha demostrado ser un problema NP-duro mal https://www.cs.utexas.edu/~klivans/crypto-hs.pdf pero en general son resolubles en la práctica.