Re: Aspiring highest-order programmer

blmblm_at_myrealbox.com
Date: 06/11/04 

Date: 11 Jun 2004 09:13:29 GMT

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 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'"?

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

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.

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.

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

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

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 ] 

-- 
| B. L. Massingill
| ObDisclaimer:  I don't speak for my employers; they return the favor.