List of (unsolved) complexity problems arising from PL
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.