[erlang-questions] erlang *****

[Alpár Jüttner]

On Tue, 2008-03-18 at 13:43 +0100, Ulf Wiger (TN/EAB) wrote:
> 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.
> > .
> 
> Oh, I thought it stood for Non-deterministic Polynomial Time.
> Where was it claimed that it means non-polynomial?

You used it above in that sense. When you say that something is NP, it
does _not_ mean it is slow or difficult to solve. Easy problems (i.e.
those are solvable in constant or in linear time) are also in NP.

Also note that NP is an attribute of (decision) problems, not
algorithms. You cannot say that an algorithm is in NP. More exactly,
there are non-deterministic polynomial time algorithms, but they run on
an unrealistic abstract machine (called non-deterministic Turing
machine), thus they are not "algorithms" in the common sense.

Regards,
Alpar

> 
> BR,
> Ulf W