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.