[erlang-questions] erlang *****

Kevin Scaldeferri kevin@REDACTED
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  
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.


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 mailing list