[erlang-questions] erlang *****

Ulf Wiger (TN/EAB) ulf.wiger@REDACTED
Tue Mar 18 13:43:19 CET 2008

Alpár Jüttner skrev:
>> This is very different from allowing a subtle change in a complex
>> pattern match to shift evaluation from constant-time or linear
>> to NP - especially when programmers have learned to expect
>> and appreciate that pattern-matching is predictable in cost.
> Once again, please: NP does _not_ mean non-polynomial, but something
> very-very different. If you want to say "worse than polynomial" you can
> say "superpolynomial" or "exponential" (if the running time is indeed
> something like O(2^n)).

Oh, I thought it stood for Non-deterministic Polynomial Time.
Where was it claimed that it means non-polynomial?

Ulf W

More information about the erlang-questions mailing list