Lista (nierozwiązanych) problemów złożoności wynikających z PL

Jakie są niektóre główne, otwarte problemy ze złożonością obliczeniową, które wynikają z języków programowania, zwłaszcza z analizy i kompilacji programów? Szukam problemów na linii „złożoności czasowej wnioskowania typu Hindleya-Milnera” lub „złożoności czasowej 0CFA” (chociaż obie są rozwiązanymi problemami).

Pippenger (1) z 1996 roku pokazuje, że (pod pewnymi założeniami) ścisłe (CBV) funkcjonalne języki programowania są asympotycznie wolniejsze niż języki imperatywne. Jest otwarte, czy wynik Pippengera można uogólnić na leniwe języki funkcjonalne, jak wskazano w (2).

Pippenger narzuca dwa założenia upraszczające (obliczenia on-line i pewną atomowość danych wejściowych). Jest otwarte, czy można je usunąć. Pippenger przypuszcza, że ​​da się to zrobić, ale ostrzega: „[s] uch wynik [...] wydaje się być daleko poza zasięgiem obecnie dostępnych metod w teorii złożoności obliczeniowej” .

Zobacz także odpowiedź Campbella w (3) i notatki Bena-Amrama (4).

^{1. N. Pippenger, Pure versus Impure Lisp .}

^{2. R. Bird, G. Jones, O. De Moor, Więcej pośpiechu, mniej prędkości: leniwa kontra chętna ocena .}

^{3. Przepełnienie stosu, wydajność czysto funkcjonalnego programowania .}

^{4. AM Ben-Amram, Uwagi na temat porównania czystego i nieczystego LISP przez Pippenger .}