Re: Aspiring highest-order programmer

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

Date: 13 Jun 2004 22:48:34 -0700

blmblm@myrealbox.com wrote in message news:<2itbdpFrmutnU1@uni-berlin.de>...
> In article <f5dda427.0406101449.296d0c4f@posting.google.com>,
> Edward G. Nilges <spinoza1111@yahoo.com> wrote:
> >blmblm@myrealbox.com wrote in message news:<2iqo8pFqegl2U1@uni-berlin.de>...
> >> In article <f5dda427.0406092312.43f8958c@posting.google.com>,
> >> Edward G. Nilges <spinoza1111@yahoo.com> wrote:
> >> >Willem <willem@stack.nl> wrote in message
> >> >news:<slrncb8ntm.25iv.willem@toad.stack.nl>...
> >> >> JKop wrote:
> >> >> ) My post was completely void of sarcasm. At first I genuniely
> thought that
> >> >> ) you were just extremely intelligent and that I simply didn't have the
> >> >> ) intelligence to understand your post... but then I just looked
> closely and
> >> >> ) decided to try understand what it was that I didn't understand, at which
> >> >> ) point I realized that I was simply unaccustomed to your language,
> and your
> >> >> ) unspecific references. Both of which make you come across, at first, as
> >> >> ) extremely intelligent.
> >> >>
> >> >> I should point out that, in the past, a lot of his pompous language and
> >> >> usage of unfamiliar verbiage has turned out to be plain wrong. He has
> >> >> never admitted this, but claims we are unable to grasp his unique usage.
> >> >> Not so recent examples include NP-completeness and fascism.
> >> >
> >> >You failed to thoroughly understand NP completeness in that
> >> >discussion, as far as I can remember. You stuck to what the text book
> >> >said.
> >>
> >> Whereas as far as I can tell from a look through Google's archives,
> >> you don't remember what the "text book said".
> >
> >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.
> >
> >The "text book" in 1971, when I started reading comp sci and took my
> >university's first class in comp sci, almost did not exist. Our "text
> >book", Sherman's Programming and Coding for Digital Computers, was
> >useless because it assumed that the university teaching the class had
> >an IBM 7094 running IBSYS as an OS and with a Fortran compiler. My
> >university had an 8K 1401 running the OS diddly squat; each program
> >carried its OS on its back.
> >
> >Another "text book" was Donald Knuth's first editions which contained
> >material on what became the theory at a later date, and, as I
> >mentioned, I recently reviewed the mat'l in Stephen Skiena's book The
> >Algorithm Design Manual.
> >
> >However, one attractive feature of computer "science" in 1971 was the
> >fact that it hadn't "matured" to the point wherein knowledge is rote
> >memorization and cutting and pasting from Wikipedia.
>
> YMMV, as they say. I got my undergraduate degrees in 1977 after
> taking (if I remember right) 9 hours of academic CS and finding it
> less than inspiring, especially compared to the math courses I was
> taking. I did more academic CS starting in 1980-something and was
> surprised to find that at that point they had many more interesting
> things to teach me and in fact seemed to be doing a lot better job
> teaching concepts rather than trivia than they did in 1970-something.
> (It was the same school, curiously enough.)
>
> Hey, if we're going to do biography.
>
> [ snip ]
>
> >> Edward, maybe I didn't read the right parts of the right discussion
> >> (I searched for postings in this group written by you and containing
> >> "NP complete" or "NP completeness", and the threads that came up were --
> >> long, very long, and not exactly focused on NP completeness). But in
> >
> >Right, because moron math is less important than other issues.
>
> More important than being sure that we all mean at least more or less
> the same thing we when use the terms of the field, "NP complete" for
> example?
>
> >> the posts I read, Willem seemed to be using "NP complete" in the way
> >> it is used in its field of origin and in one of his posts provided
> >> a link to a definition/discussion in the comp.theory FAQ. I don't
> >> get the sense from the way you use the term that you've read this
> >> formal definition, and you seem not to have explained anywhere what
> >> you think it means. Why don't you do so? You seem to be claiming
> >
> >See separate post
>
> Um. Yes, I read that one, and if you claim that in it you told us
> what you think "NP complete" means, my paraphrase would be that you
> think "an NP-complete algorithm is one whose running time is O(n*n)."

If I said that it is wrong. An NP algorithm, as Ian reminded us, is
one whose execution time formula is not a polynomial. n*n is a
polynomial. End of story.

> If that's what you meant -- this is almost laughably far from the
> accepted definition of the term, and IMO misses the point completely.
> More about that later in this reply. If that's not what you meant,
> maybe you'd be willing to try again to just answer the question
> "what do you think is meant by 'NP complete'"?

I think the accurate term is NP, not NP complete, in light of the
discussion. NP completeness is a property of mathematical objects. But
as I have said, I am not qualified on this because I don't work with
it...although one of my CS profs did an excellent job of describing
the "state of the art" in 1976.

And as I have said, no practical programmer can afford to be much
interested in programs whose execution time formula increases more
rapidly than the polynomial x*x, for the simple reason that O(x*x)
algorithms already suck.

And as I have said, it is to me a sign of the decadence of CS that
focus is on this arcana when we still don't have halfway decent
programming languages.

>
> >> to have a practical understanding of the underlying ideas that's
> >> more valuable to a working programmer than any formal definition.
> >> Could be. What is it?
> >
> >When I encountered the theory in Knuth (who is to me of far greater
> >stature than most younger computer scientists, in part because he does
> >his own goddamn programming and is man enough to admit error) it was
> >in the context of "aha" rather than the context of "ho hum".
> >
> >The context of "aha" is where a "theory" makes sense because you see
> >its instantiation in the real world.
> >
> >O(n*n) is where the program starts slowing down for larger inputs and
> >in the real world it means "it works in test, why is the user hopping
> >mad?"
> >
> >O(n) is where the program runs at constant speed.
>
> "Constant speed"? Usually "O(n)" means that execution time is roughly
> proportional to "problem size" (e.g., the number of elements in an
> array to be searched using sequential search). Execution time is
> thus *a linear function of the size of the problem/input*, but not
> *constant*.

Constant speed in the sense, of course, of a constant rate of
deceleration.

It sounds to me that participants in this discussion know about NP
completeness but don't have a feel for calculus in the sense of being
able to tell, from a practical program's graph of execution time, the
derivative of its execution time formula by feel. Since I sucked at
calculus but can do this, I tremble for the future.

O(n) is what you want for most programs.

>
> If your point was that an O(n*n) function grows (as n increases, and
> for sufficiently large n) more rapidly than an O(n) function, yes,
> agreed.
>
> If your point was that for large inputs one should prefer an O(n)
> algorithm to an O(n*n) algorithm, also agreed, all other things
> being more or less equal. If your point was that O(n*n) algorithms
> are fine when readability is more important than execution time and
> inputs are small, also agreed.
>
Cool. We're just sailing along merrily,
 
> But the thing is, O(n*n) algorithms are not horrible -- yes, they're
> "slower" in some meaningful sense than O(n) algorithms, but an O(n*n)
> algorithm is still reasonable for pretty large inputs.
>
Not in the real world. Graph the execution time formula willya.

O(n*n) behavior causes the well-known crisis that occurs when the test
team thinks the code works and hands it off to the user. The user
subjects the code to large n, and the system slows to a crawl.
 
> O(n!) (n factorial) algorithms, though, really *are* horrible --
> for sufficiently large n, an O(n!) algorithm will grow faster than
> any polynomial-time algorithm, and indeed an O(n!) algorithm isn't
> going to be practical even for numbers that aren't typically regarded
> as large (three digits maybe? I admit I can't be bothered to do the
> arithmetic right now, but I was told once that solving the classic
> traveling salesperson problem by brute force was only practical for
> n <= about 300).
>
OK
 
> The theory of NP completeness is related to all of this, but to
> some extent a different ball of wax. As another poster said, NP
> completeness is a property of problems, not algorithms. I mean,
> I can come up with an O(n!) algorithm for sorting, but that doesn't
> make sorting an O(n!) problem. The best known sorting algorithm is

No, it makes you the proud creator of a solution that sucks. I've been
there, so this is not a flame.

> -- hm, I think there are some subtle details I'm not remembering
> here, but I think in general it can be proved that you can't do
> much better than O(n log n)? Now, *that*'s kind of interesting,

n log n is sweet. Again, graph it. The rate of acceleration slows
down.

> no? The executive-level summary version of why NP completeness
> is interesting is this: There are problems that are "intractable"
> (not solvable in reasonable time for more than small inputs) because
> there is no known polynomial-time algorithm to solve them and good
> reason to suspect that no such algorithm exists. (I trust that one
> of the theory-oriented regulars will jump in and correct me if
> I didn't get this quite right.)
>
> [ snip ]
>
> >You "waded" through usenet postings and found nothing to confirm or
> >deny a pro or anti view. This is because most of the sludge was
> >created, I am now convinced, by people who use this ng not for the
> >purpose it was intended but to shore up shaky senses of self-worth by
> >abusing newbies and outliers.
>
> I wasn't looking for pro-anything or anti-anything views; I was looking
> first for posts in which you said "when I say NP complete, I mean ....",
> and after not finding such a post I looked for posts in which you used
> the phrase, hoping to guess from usage what you thought it meant.
>
> >Part of the "maturation" process of any field is in fact the
> >elimination of charlatans, snake oil salesmen and quacks. When I
> >started out in compsci, one of the superficially attractive features
> >of the field was in fact its domination by amiable rogues, but today
> >one of its depressing features is the absence of same. The problem is
> >that today, knowledge production in the field has been formalized to
> >the extent that knowledge becomes like wisdom in the Bible as mediated
> >by Prince Hal in Henry IV: "thou sayest well, for wisdom crieth out in
> >the streets, and no man pays it any mind".
> >
> >Prince Hal is commenting on Shakespeare's Falstaff, who has told the
> >Prince that the Lord Chief Justice, Falstaff's nemesis, had berated
> >him in the streets, and the Henry trilogy in Shakespeare is a
> >meditation on the costs and benefits of political "maturity".
> >
> >Falstaff, like an old time computer consultant, is one of those
> >bullshitters who occasionally comes up with a useful insight. But the
> >problem for students is that their sources of knowledge have to be
> >accepted by society as a whole.
> >
> >Thus any recount "in my own words" of NP completeness is suspect
> >without editing and review.
>
> I have no idea what you mean by this, and I wasn't even sure what
> parts I could snip out and still retain what was germane to the point
> I want to make next, so I left it all in. I also don't think it would
> be useful or entertaining to try to figure it out, so I'll just say
> my piece: I belong to the school of thought that claims that if you
> can't explain a concept in your own words to a minimally-prepared
> audience you probably don't understand it very thoroughly. So IMO
> the request that you explain in your own words what you mean by the
> terms you're using is more than reasonable.

This discussion has been for me a refresher class in a theory which I
learned but seldom had reason to use, since I don't like to code even
solutions of order n*n. And since my resume contains a disclaimer
saying I Won't Work anymore for oil companies, I guess I've taken
myself out of the running for a million bucks in solving the problem
of the relation of P and NP, which may be of interest primarily to big
energy.

But I will say this.

In the 1950s, halfway decent programmers could and did write a simple
binary search and some of them INVENTED quick sorting and other
sorting algorithms, as programmers and not as university faculty.

Today, many people who call themselves programmers could not code a
binary search if their lives depended on it.

This meanwhile the CS academics are playing with the properties of
unusable algorithms instead of teaching the kiddies the basics of good
programming, "good programming" having been regarded since Johnny von
Neumann as at best a harmless pursuit for doltish fellows, at least in
England and America.

There are exceptions, and ironically they are in the most "academic"
venues. Brian Kernighan at Princeton attempts to show the future Best
and Brightest that programming is indeed more than a matter for
doltish fellows, and Dave Hansen at the same venue told me that he
regarded actual programming in real languages as challenging.

The problem is that a false intellectual class structure is generated
and maintained, perhaps more at the anxious middle of academia, that
boundary between the bottom feeders and the zenith which patrols
itself.

Actually refusing, as Dijkstra refused, to separate theory and praxis
violates the rules of the game in which academic self-reproduction
becomes more important than mere teaching and research for usable
solutions as opposed to cites.

All of this is just me blowing off a concern I've had for some time,
as I have watched CS and software "mature" from something fun and
exciting to a matter for Dead Souls and the generation of boredom
opportunities at warp speed. None of this should be read as an excuse
for my errors concerning NP completeness.

I am excited about the ability to parse at a "low" level using
compiler design techniques as opposed to just randomly blasting away
with yacc because I think that the grassroots generation of "little
languages" is a solution to real problems I have encountered in the
real world.

But as to algorithms that take factorial time, in the practical sense
they represent nothing but trouble.

Thanks to your contribution and that of Ian I will endeavor in future
to use correct language on this matter all the same.
>
> You seem to think that using technical terms in their accepted senses
> and being able to produce definitions of mathematical terms that are
> reasonably mathematically literate constitutes "rote memorization".
> I won't argue that there's a lot of rote memorization going on in a
> lot of fields, but the phrase I'd use for using technical terms, etc.,
> and being able to produce, etc., is "doing your homework before starting
> to hold forth".
>
> [ snip ]