[erlang-questions] erlang *****
Andras Georgy Bekes
Tue Mar 18 14:28:20 CET 2008
> 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". It was used
instead of NP-hard, which means it is very unlikely to find an algoritm
that runs in polynomial time.
The problem is probably NP complete, which means "is in NP" AND "is NP
More information about the erlang-questions