[erlang-questions] erlang *****

[Alpár Jüttner]

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

NP is a class of decision problems (yes or no answer). (A "problem" is
typically given as the set of problem instances for which the answer is
yes.)  For example, the graphs containing Hamiltonian cycles is in NP.
But if I tell you that "yes, the a graph contains a Hamiltonian cycle,
will you be able to check it? Probably not.

On the other hand: contrary to your definition, NP is not symmetric. If
a problem is NP, its negated version is not necessarily in NP. If fact,
if you can proof that both are NP, you can suspect that your problem is
actually in P.

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'.

A bit more precisely, the problem is in NP if there is a polynomial time
algorithm A that requires a problem instances I, and a certificate C as
input and
      * if the answer is 'yes' for I, there exists a certificate C for
        which A(I,C) answers 'yes', but
      * (we cannot be cheated) if the answer is 'no', then there cannot
        exists such an C.

This certificate is sometime very straightforward, sometimes it is not.
Two examples:
      * Hamiltonian cycles
              * It is in NP: if you give an H-cycles in the graph, it is
                a good certificate.
              * Is it in co-NP? We don't know, but probably not. Nobody
                knows a certificate that would prove that a graph has no
                Hamiltonian cycle.
      * Prime numbers
              * It is in co-NP: if you give a divisor of a number, than
                it will proof that the number is not prime (we can check
                in P that it is a real divisor).
              * Is it in NP? YES, but here the good certificate is not
                straightforward at all, it was invented in 1975 by
                Vaughan Pratt.
              * In fact, there exists a deterministic polynomial
                primality test algorithm called AKS-test, but it was
                invented only 2002.

>   NP is often used in a "vernacular" sense,
> meaning (real NP) \ P.

Never by those are familiar with the Complexity theory.

If you show me a single problem in (real NP) \ P, I shut up immediately.
But up to my knowledge, nobody could show such a problem, so it is more
than useless to use NP in this sense.

I still believe that this kind of misuse of NP is rooted in the
misconception that NP means non-polynomial. This kind of mistake is
typically taken quite seriously in an undergraduate course in Complexity
theory. It is something similar as if "I had six heads in line, so the
next one must be a tail because of the _theory_of_large_numbers_" were
said on an oral exam in Probabilistic theory.

To sum up:
      * If you want to say that a problem is not in P, say that. Non-P
        is not really longer that NP and it is correct.
      * If you want to say that "it is hopeless to find a polynomial
        time algorithm for solving is, because it is at least as hard to
        solve that any other NP problem", say that it is NP-hard (or
        NP-complete).

Best regards,
Alpar


> 
> > However, if pattern matchings are done one-by-one
> 
>   why should they be?
> 
> > and left-to-right,
> 
>   why on earth should they be?
> >
> > then there is no performance problem.
> 
> That is, you are proposing that
> 	f(P1 \/ P2, P3 \/ P4) -> B
> should be treated like this Prolog version:
> 	f(X, Y, Ans) :-
> 	    (X = P1, ! ; X = P2, !),
> 	    (Y = P3, ! ; Y = P4, !),
> 	    B'(Ans)
> rather than like this Prolog version:
> 	f(X, Y, Ans) :-
> 	    (X = P1 ; X = P2),
> 	    (Y = P3 ; Y = P4),
> 	    !,
> 	    B'(Ans).
> 
> 
> > The union operator becomes less
> > flexible in this case, but it is still quite useful.
> 
> It may be slightly useful on rare occasions, but it would be
> *extremely* confusing.  The interaction with guards is really
> quite nasty.  Take an example:
> 
> 	f({X,_}\/{_,X}, {Y,_}\/{_,Y}) when X > 0, Y > 0 -> {X,Y}.
> 
> with the call
> 	T = {-1,2}, f(T)
> 
> It's obvious that f(T) should return {2,2}.  Under the "backtracking"
> translation, where the "->" of Erlang corresponds to the "!" of Prolog,
> it's even true.  But under the "choice always cuts" model, it fails.
> Try explaining *that* to an Erlang novice.
> 
> It is OK for programming language constructs to be clumsy and limited
> in power.  It is not OK for them to be stark raving mad.
> 
> The only time that the local commit model makes sense is when the
> disjunctive pattern binds no variables.  An extension of Erlang to
> allow P1\/P2 precisely when P1 and P2 contain no variables other
> than wild-cards *would* be reasonably trouble-free, except that we
> would have a continuing stream of people proposing that it be  
> generalised.
> 
> 
> >
> >
> > Actually, if we want the pattern matching to be deterministic, we  
> > _must_
> > do such a restriction. For example using the patter {X,_} V {_X}, the
> > value of X could be either element of the tuple. Using the left-to- 
> > right
> > rule, X will always be the first element.
> >
> > Regards,
> > Alpar
> >
> >
> 
> --
> Te Reo Engarihi is a taonga of Te Iwi Pakeha,
> ergo we should keep it pure, sans mélange, ruat caelum.
> 
> 
> 
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions