From: Fan Li TAI <UFLTAI%MEMSTVX1.bitnet@CUNYVM.CUNY.EDU>
Date: Wed, 2 Dec 92 21:50:52 PST
To: cypherpunks@toad.com
Subject: enjoy enjoy
Message-ID: <9212030550.AA06424@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


Hiya,
        Below's something I found...  I know you all have been swamped with
mail... but this one is in the spirit of things, I think...  Found it in
Life...

____begin____
From: sherman@.cs.umbc.edu (Dr. Alan Sherman)
Subject: Superpolylogarithmic Subexponential Functions
Newsgroups: rec.music.dementia

Announcing: Technical Report TRCS-91-17, University of Maryland
Baltimore County.  A preliminary version of this paper appeared in two
parts in {\it SIGACT News}, {\bf 22}:1 (winter 1991), Whole Number~78,
65--73, and {\bf 22}:2 (spring 1991), Whole Number~79, 51--56.


        On Superpolylogarithmic Subexponential Functions

                        Alan T. Sherman
                Computer  Science Department
                University of Maryland Baltimore County
                Baltimore, Maryland 21228
                        and
                Institute for Advanced Computer Studies
                University of Maryland College Park
                College Park, Maryland 20742

                June 21, 1990 (revised April 1, 1991)


                        Abstract

A superpolylogarithmic subexponential function is any function that
asymptotically grows faster than any polynomial of any logarithm but
slower than any exponential.  We present a recently discovered
nineteenth-century manuscript about these functions, which in part
because of their applications in cryptology, have received
considerable attention in contemporary computer science research.
Attributed to the little-known yet highly-suspect
composer/mathematician Maria Poopings, the manuscript can be sung to
the tune of ``Supercalifragilisticexpialidocious'' from the musical
Mary Poppins.  In addition, we prove three ridiculous facts about
superpolylogarithmic subexponential functions.  Using novel extensions
to the popular DTIME notation from complexity theory, we also define
the complexity class SuperPolyLog/SubExp, which consists of all
languages that can be accepted within deterministic
superpolylogarithmic subexponential time.  We show that this class is
notationally intractable in the sense that it cannot be conveniently
described using existing terminology.  Surprisingly, there is some
scientific value in our notational novelties; moreover, students may
find this paper helpful in learning about growth rates, asymptotic
notations, cryptology, and reversible computation.

Keywords. Algorithms, asymptotic notation, complexity theory,
cryptography, cryptology, DTIME, mathematical humor, Maria Poopings,
Mary Poppins, musical computer science, reversible computation,
Supercalifragilisticexpialidocious, superpolylogarithmic
subexponential functions, SuperPolyLog/SubExp.

                --- lyrics ---

            Superpolylogarithmic Subexponential Functions
    (Sung to the tune of ``Supercalifragilisticexpialidocious.'')

Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!

Superpolylogarithmic subexponential functions!
Faster than a polylog but slower than exponential.
Even though they're hard to say, they're truly quintessential.
Superpolylogarithmic subexponential functions!

Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!

For Alice to send a message through to Bob when Eve's eavesdropping,
do use a trapdoor one-way function---not a one-key mapping.
First take a message x, let's say, and raise it to the e;
then mod it out by p times q but keep these secretly.  Oh!

(Chorus)

Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!

The process takes but poly-time and appears to be secure:
why even just a single bit is one over polylog pure.
Though Alice thinks that Eve must spend time at least exponential,
by using Lenstra's elliptic curves, Eve splits n subexponentially.  Oh!

(Chorus)

Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!

we remove the heat with water but there's a better strategy.
Since thermodynamics does not apply when info is not doomed,
the laws of physics don't require that power be consumed.  Oh!

(Chorus)

Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!

Now Bennett said in `73, to run a program P,
you simulate the program P, but do so reversibly.
The problem with this method is that space is exponential,
so trade off time to save on space---this really is essential! Oh!

(Chorus)

Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!

Did you know if you invert one, you get a
funtionential subexporithmic logapolyrepus?
But that's quite a singularity!  So,

If you are in an oral exam and cannot find the way,
just summon up these words and then you've got a lot to say.
But better use them carefully or you could fail the test.
A professor once asked me,
``What do you call functions that grow faster than any
polylogarithm but slower than exponential?'' There're,

Superpolylogarithmic subexponential functions!
Superpolylogarithmic subexponential functions!
Superpolylogarithmic subexponential functions!
Superpolylogarithmic subexponential functions!

                --- end of lyrics ---

Note: See paper for detailed performance notes and mathematical
proofs by anagramming.