[erlang-questions] erlang *****
Wed Mar 19 16:06:49 CET 2008
Is it possible we can all agree this debate has reached a sufficient
level of pedantry that those who really want to debate can take it off-
list? It feels like people area being argumentative just for the sake
On Mar 19, 2008, at 4:41 AM, Alpár Jüttner wrote:
>> NP means "non-deterministic polynomial" and is most simply thought of
>> as "answers can be checked in polynomial time but not necessarily
>> found in polynomial time". NP includes P.
>> I expect we all know that.
> Hopefully not, because this is a wrong definition.
> The right (still intuitive) definition is this:
> A problem is NP if for all 'yes' problem instance there exists a
> certificate the help of which we can check/proof (in polynomial time),
> that the answer is 'yes'.
This, I believe, is precisely what was meant by the above.
>> NP is often used in a "vernacular" sense,
>> meaning (real NP) \ P.
> Never by those are familiar with the Complexity theory.
The use of the term "vernacular" strongly suggests that he understands
there is additional subtlety.
PS - It seems to me that no-one has actually tried to debate the
original assertion that such-and-such extension to pattern matching
would turn it into an NP (hard) problem. Instead everyone seems to
have jumped on whether the OP understood what NP means or not.
More information about the erlang-questions