Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re^4: Perl 6 rules and complexity

by fergal (Chaplain)
on Feb 18, 2006 at 13:07 UTC ( [id://531143]=note: print w/replies, xml ) Need Help??


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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?

www.com | www.net | www.org
Node Status?
node history
Node Type: note [id://531143]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? • Last hour • Other CB clients
Other Users?
Others avoiding work at the Monastery: (5)
As of 2024-04-19 22:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found