Quais são alguns dos principais problemas de complexidade computacional aberta que surgem das linguagens de programação, especialmente a análise e compilação de programas? Estou procurando problemas nas linhas "da complexidade temporal da inferência do tipo Hindley-Milner" ou "da complexidade temporal de 0CFA" (embora ambos sejam problemas resolvidos).
17
Respostas:
Pippenger (1), de 1996, mostra que (sob algumas suposições) as linguagens de programação funcional estritas (CBV) são assintoticamente mais lentas que as linguagens imperativas. Está aberto se o resultado de Pippenger pode ser generalizado para linguagens funcionais preguiçosas , como apontado em (2).
Pippenger impõe duas suposições simplificadoras (computação on-line e uma certa atomicidade de entrada). Está aberto se eles podem ser removidos. Pippenger conjetura que isso pode ser feito, mas alerta: "[...] um resultado parece muito [...] além do alcance dos métodos atualmente disponíveis na teoria da complexidade computacional" .
Veja também a resposta de Campbell em (3) e as anotações de Ben-Amram (4).
1. N. Pippenger, Pure Versus Impure Lisp .
2. R. Bird, G. Jones, O. De Moor, Mais pressa, menos velocidade: avaliação preguiçosa versus ansiosa .
3. Stack Overflow, eficiência de programação puramente funcional .
4. AM Ben-Amram, notas sobre a comparação entre Pippenger e LISP puro e impuro .
fonte