Re^3: Perl 6 rules and complexity

[zby]

To put that in context - it is known that type inference in languages like ML is DEXP Time complete (http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=96748, my Masters Thesis was a modified proof of that :))

[fergal]

That might be in context but it's not a context that I'm the least bit familiar with!

DTIME and DEXPTIME don't seem to have a lot of material about them on the web or at least they don't seem to have many introductions to the terminology. wikipedia and some lecture notes are the closest I could find.

Apart from being a performance guarantee for a specific model of computation, rather than an asymptotic guarantee, how is DEXPTIME different from O(2^n)? Is it any worse or better. Is it just more precise or am I wrong to interpret DEXPTIME as DTIME(some exponential function)?

[zby]

DEXPTIME is Deterministic Expotential Time ie it is the same as O(2^n) for time (time is the most frequently used measure of complexity but there are others and among them is space). So I really should have written that ML grammar is expotential in the worst case too.