Very large computational complexity classes like ELEMENTARY and PR are not important because at that point you're usually limited to only being able to compute the problem on tiny instances, so asymptotics as input size approaches infinity is not relevant.
Ok, I don't actually know what any of this is. What is the sense of "optimal" in which optimal reduction of lambda calculus terms corresponds to ELEMENTARY?
-
-
The optimal reduction algorithm is optimal in the sense that it always chooses the evaluation order (strict/lazy) that results in the fastest execution time. The algorithm just doesn't work on terms whose reduction takes longer than ELEMENTARY time. https://dl.acm.org/citation.cfm?id=96711 …
-
https://pdfs.semanticscholar.org/c161/2cc3dcfb04169cfd353dcf546aaf3ef81fcc.pdf … details the relationship between EAL and Lamping's algorithm. I'm not sure whether there are non-EAL-typeable lambda terms that Lamping can evaluate, but most evaluable terms are EAL-typeable.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.