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