[erlang-questions] erlang *****

Andras Georgy Bekes bekesa@REDACTED
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 
hard".

	Georgy



More information about the erlang-questions mailing list