[erlang-questions] erlang *****
Wed Mar 19 19:54:17 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.
I didn't debate on anything.
I'm not an expert in Erlang, not even a professional software developer.
If I say something stupid about it or do a wrong assumption, the list
members kindly fix my error and I'm happy with it.
What happened now, is that someone who is not expert in the complexity
theory used a terminus technicus in a very wrong way, and I fixed it.
I apologize if it was too boring or annoying for you or for others.
P.S. For me, it is at least a strange way of communication to comment a
post publicly and ask to continue it off-list at the same time.
> 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