¿Cuáles son algunos de los principales problemas de complejidad computacional abierta que surgen de los lenguajes de programación, especialmente el análisis y la compilación de programas? Estoy buscando problemas en las líneas de "la complejidad temporal de la inferencia de tipo Hindley-Milner" o "la complejidad temporal de 0CFA" (aunque ambos son problemas resueltos).
17
Respuestas:
Pippenger (1) de 1996 muestra que (bajo algunos supuestos) los lenguajes de programación funcional estrictos (CBV) son asintóticamente más lentos que los lenguajes imperativos. Está abierto si el resultado de Pippenger se puede generalizar a lenguajes funcionales perezosos , como se señaló en (2).
Pippenger impone dos supuestos simplificadores (cálculo en línea y una cierta atomicidad de entrada). Está abierto si se pueden quitar. Pippenger conjetura que se puede hacer, pero advierte: "[s] uch un resultado [...] parece estar más allá del alcance de los métodos disponibles actualmente en la teoría de la complejidad computacional" .
Ver también la respuesta de Campbell en (3), y las notas de Ben-Amram (4).
1. N. Pippenger, Pure Versus Impure Lisp .
2. R. Bird, G. Jones, O. De Moor, Más prisa, menos velocidad: evaluación perezosa versus ansiosa .
3. Desbordamiento de pila, eficiencia de la programación puramente funcional .
4. AM Ben-Amram, Notas sobre la comparación de Pippenger de LISP puro e impuro .
fuente