[erlang-questions] erlang *****

[Kevin Scaldeferri]

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  
of it.


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.


-kevin

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.