[erlang-questions] erlang *****

Ulf Wiger (TN/EAB) ulf.wiger@REDACTED
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).

Ulf W

More information about the erlang-questions mailing list