Daftar masalah kompleksitas (yang belum terpecahkan) yang muncul dari PL

Apa saja masalah kompleksitas komputasi utama dan terbuka yang muncul dari bahasa pemrograman, terutama analisis dan kompilasi program? Saya mencari masalah pada baris "kompleksitas waktu inferensi tipe Hindley-Milner" atau "kompleksitas waktu 0CFA" (meskipun keduanya merupakan masalah yang diselesaikan).

Pippenger's (1) dari tahun 1996 menunjukkan bahwa (di bawah beberapa asumsi) bahasa pemrograman fungsional yang ketat (CBV) secara asympotically lebih lambat daripada bahasa imperatif. Sudah terbuka apakah hasil Pippenger dapat digeneralisasikan ke bahasa fungsional yang malas , seperti yang ditunjukkan dalam (2).

Pippenger memaksakan dua asumsi penyederhanaan (perhitungan on-line, dan atomicity input tertentu). Terbuka apakah mereka dapat dihapus. Pippenger menduga bahwa hal itu dapat dilakukan, tetapi memperingatkan: "[s] uch hasilnya [...] tampaknya jauh melampaui jangkauan metode yang saat ini tersedia dalam teori kompleksitas komputasi" .

Lihat juga jawaban Campbell dalam (3), dan catatan Ben-Amram (4).

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

^{2. R. Bird, G. Jones, O. De Moor, Lebih tergesa-gesa, lebih cepat: evaluasi malas versus bersemangat .}

^{3. Stack Overflow, Efisiensi pemrograman murni fungsional .}

^{4. AM Ben-Amram, Catatan tentang Perbandingan Lipp Murni dan Tidak Murni Pippenger .}