Re: Aspiring highest-order programmer

From: Edward G. Nilges (spinoza1111_at_yahoo.com)
Date: 06/12/04 

Date: 12 Jun 2004 05:55:31 -0700

Ian Woods <newspub2@wuggyNOCAPS.org> wrote in message news:<Xns950627D054FDEnewspubwuggyorg@217.32.252.50>...
> spinoza1111@yahoo.com (Edward G. Nilges) wrote in
> news:f5dda427.0406111715.40a601fa@posting.google.com:
>
> > Christopher Barber <cbarber@curl.com> wrote in message
> > news:<psozn7arxca.fsf@unicron.curl.com>...
> >> spinoza1111@yahoo.com (Edward G. Nilges) writes:
> >>
> >> > I have replied separately to your request that I describe my
> >> > understanding of the applied theory of NP-completeness. It was
> >> > probably a mistake to do so, since anything other than what on
> >> > usenet corresponds to moronized rote memorization (cutting and
> >> > pasting a Wikipedia) will be "deconstructed" in a Sophistical, but
> >> > moronic, fashion, to "prove" that "he doesn't know what he's
> >> > talking about", when I do.
> >>
> >> You have so far not yet proved that you understand what NP-complete
> >> means. That is nothing to be ashamed of, it is a somewhat esoteric
> >> concept for most programmers, but from what you have posted so far,
> >> you don't seem to truly understand what it is about.
> >
> > You are playing a game that derives from the fact that during my long
> > career, "intellectual" "property" considerations have transformed
> > active knowledge into dead secrets in such a way that one can never,
> > in an exchange like this, "prove" that he or she has human knowledge.
>
> The concepts of NP, NP-complete and NP-hard can be found in a vast amount
> of freely available information, either through the power of that
> Internet thingummy, or by referring to the wealth of papers published on
> them over the last 40-ish years. They're so basic they're even taught to
> students studying software engineering and computer science. They're not
> exactly a trade secret.
>
> > The reason is alienation. IP concerns are that knowledge becomes part
> > of inventory and in this context, an unalienated individual making
> > knowledge claims independent of the organization can always be
> > renarrated as at worst not having "knowledge" and at worst as a
> > charlatan.
> >
> > The interesting result is that mentoring disappears and is replaced by
> > ideological training and indoctrination. The interesting result is
> > that today's programmers repeat the mistakes of the past because their
> > elders aren't man enough any more to make knowledge claims lest some
> > suit or some fat woman from human resources "expose" the "hollowness"
> > of their claims.
> >
> > The corporate game is that you are "human resources" and you don't
> > understand the theory, therefore anything I say can be and will be
> > misread.
>
> You don't exactly help the situation by going that extra mile to make
> everything you say more difficult for your audience to understand.
>
> <snip>
> >> Of course, that would be expected if they are writing code that
> >> solves an NP-complete problem. If you mean that inexperienced
> >> programmers may sometimes use bad algorithms, I am sure I would
> >> agree, but you should not use the terminology "NP complete fashion"
> >> to describe this. NP completeness refers to a property of the
> >> problem domain, not the algorithm choosen to solve it.
> <snip>
> > The academic meaning "this problem is solvable only by an algorithm
> > whose efficiency formula is nonpolynomial" has been transformed by
> > recent usage (and only usage) to mean that the PROBLEM is "np
> > complete" or "np" but the definition implies the existence of the
> > overcomplex algorithm.
>
> For NP, it means that there is no known polynomial time algorithm to
> solve the problem. For NP-complete (where all the NP problems in that set
> are 'equivalent'), the moment someone comes up with a polynomial time
> algorithm to solve any NP-complete problem, all NP-complete problems can
> be solved in polynomial time. (It would mean that someone had effectively
> proved that the set of NP complete problems is in the set of problems
> which can be solved in polynomial time... which would be one hell of an
> accomplishment, and worth at least a million dollars last time I
> checked.)
>
> In other words, and back to your point, it's the /lack/ of existence of a
> polynomial time algorithm to solve the problem which makes the problem
> believed to be part of set of NP problems.
>
> > In place of understanding you are instead demanding adherence to a
> > pragmatic terminology which is merely praxis.
>
> It's a formal definition which has been around since the 1960's and is
> well understood by well read (and, like me, not so well read) computer
> scientists and related people.
>
> In place of incorrect usage of specific terminology, I for one would
> prefer correct usage of that terminology.

Thanks for an excellent precis of what I know but am completely not
qualified to describe, and thanks for your courtesy.

If algorithms of polynomial time order 2 (O(n**2+m+k)=O(n*n) when
m=k=0) are too slow for practical use as the number of input data
points increases, problems that cannot be solved in polynomial time at
all would seem to me, as a nonspecialist in these matters, to be
useless. And would it be truly worth a million dollars to discover
that all NP complete and therefore equivalent problems have an
algorithm whose complexity formula is a polynomial?

Doesn't this fail to answer the question as to the practicality of the
rank of the polynomial.

I've read versions of the theory between reading Knuth in 1971 and
Skiena in 1999 and the REASON Knuth and Skiena stood out is their
practical application.

Relevant Pages

  • Re: Why isnt NP simply "not polynomial"?
    ... Why can't NP be defined as the class of decision problems ... It is certainly possible to define a class Not-P (I'll use a different ... there is no *known* polynomial time algorithm. ...
    (comp.theory)
  • Re: Distance normalized TSP algorithm
    ... have not seen it applied to TSP, but I suspect that is mainly because it ... more challenging than that, but perhaps a bit less challenging than ... finding a polynomial time algorithm for an NP-complete problem. ...
    (comp.lang.java.programmer)
  • hi guys...need insight into this interesting algorithm..Repost
    ... I need to devise a polynomial time algorithm which given an integer ... returns a spanning tree with m number of 'A' labelled edges and ...
    (sci.math)
  • Interesting algorithm...need insights..
    ... I need to devise a polynomial time algorithm which given an integer ... returns a spanning tree with m number of 'A' labelled edges and ...
    (sci.logic)