List of (unsolved) complexity problems arising from PL What are some major, open computational complexity problems that arise from programming languages, especially program analysis and compilation? I am looking for problems on the lines of "the time complexity of Hindley-Milner type inference" or "the time complexity of 0CFA" (though both are solved problems).
Pippenger's (1) from 1996 shows that (under some assumptions)  strict (CBV) functional programming languages are asympotically slower than imperative languages.  It is open whether Pippenger's result can be generalised to lazy functional languages, as was pointed out in (2).

Pippenger imposes two simplifying assumptions (on-line computation, and a certain atomicity of input). It is open whether 
they can be removed.  Pippenger conjectures that it can be done, but warns: "[s]uch a result [...] seems far beyond the reach of currently available methods in computational complexity theory".

See also Campbell's answer in (3), and  Ben-Amram's notes (4).




 1. N. Pippenger, Pure Versus Impure Lisp.



 2. R. Bird, G. Jones, O. De Moor, More haste, less speed: lazy versus
    eager evaluation.



 3. Stack Overflow, Efficiency of purely functional programming.



 4. A. M. Ben-Amram, Notes on Pippenger's Comparison of Pure and Impure LISP.