[erlang-questions] erlang *****
Ulf Wiger (TN/EAB)
Tue Mar 18 14:57:07 CET 2008
Andras Georgy Bekes skrev:
>> Oh, I thought it stood for Non-deterministic Polynomial Time.
>> Where was it claimed that it means non-polynomial?
> It was used in that sense.
> If you think about it: X is (in) NP means a "good" thing: it means that
> for solving X we have an algorithm that runs in exponential time,
> however, there might be better algorithms.
> In this thread, it was constantly used as something "bad".
In the context of pattern-matching, I thought exponential
time was pretty bad. The "there might be better algorithms"
part might be reason enough to keep the discussion going. (:
It was mentioned in another post that pattern-matching is
atomic in the VM. That's correct - the VM will not schedule
another process while inside a pattern match (except, of
course, in the SMP version, where other schedulers might).
More information about the erlang-questions