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).

  • 5
    $\begingroup$ Why the vote to close? If this question is "too broad", tons of other questions on this site should be closed. $\endgroup$ – Damiano Mazza Feb 26 '18 at 11:17
  • $\begingroup$ One I’m interested (but I am not sure if it is unsolved) is using (non-closed) Beta distance of lambda terms from a ground term as a measure of complexity. $\endgroup$ – Samuel Schlesinger Mar 18 '18 at 16:31

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.