[erlang-questions] erlang *****

Alpár Jüttner alpar@REDACTED
Tue Mar 18 14:53:43 CET 2008


> The problem is probably NP complete, which means "is in NP" AND "is NP 
> hard".

Strictly speaking, an NP (and therefore an NP-complete) problem must be
a decision problem. So, if you want to check if a pattern matches (yes
or no answer), then your problem is NP-complete. If you want to find the
actual binding of the variables, then your problem is NP-hard. Anyway,
this doesn't matter too much: NP-hard is a good notation for everything,
and it expresses the fact, that it is _hopeless_ (but not proved to be
impossible!) to find a provable fast (i.e. polynomial) algorithm for the
problem.

Regards,
Alpar


> 	Georgy
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions




More information about the erlang-questions mailing list