in reply to Re^3: Perl 6 rules and complexity
in thread Perl 6 rules and complexity

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

Replies are listed 'Best First'.
Re^5: Perl 6 rules and complexity
by zby (Vicar) on Feb 18, 2006 at 16:41 UTC
    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.
[reply]

In Section Seekers of Perl Wisdom