The ACSU Versus the Evil Professor Theoryborg: A Tale of High Adventure and Low Address Bits

by Scott Aaronson

March 4, 2000


Note: ACSU stands for Association of Computer Science Undergraduates.

 

All ye who wish to partake in the journey:

·         You must be an undergraduate enrolled at Cornell.  PhD and MEng students, sorry.

·         You must work individually.

·         There are 5 questions, each of which has a positive integer for an answer.  If you think you’ve answered a question, write down the integer on your answer sheet and raise your hand, and an officer will come by to check.

·         You can use any programming language you want.  You don’t need to submit your programs.

·         The competition runs from 9:30AM until 12:59PM.  Questions answered correctly from 9:30 to 9:59 are worth 15 points, those answered from 10:00 to 10:29 are worth 14 points, those answered from 10:30 to 10:59 are worth 13 points, and so on.

·         Each time you answer a question incorrectly, 4 points are deducted from the score you’ll get if you answer it correctly later on.

·         You may use programming textbooks, but may not communicate with anyone else.

·         Prizes will be awarded to the top three scorers, with ties broken randomly.

·         Don’t look for connections between the CS-related jokes in the questions and the questions themselves.  There aren’t any.

 

Introduction

 

Five AM, Monday morning, CSUGLAB.  The second-to-last masochistic CS student bailed out an hour ago, leaving you alone amid the rows of humming NT boxes.  As the first rays of sunlight trickle onto your unwashed face, you become increasingly unable to concentrate on the bug-infested labyrinth of Java code before you.  You spin around in your chair, run laps from one end of the lab to the other, make funny faces at the security camera.

            Given your semi-delirious condition, when a six-inch fairy sporting an ACSU t-shirt materializes in the air in front of you, you quickly dismiss her as an all-nighter-induced apparition.  But after she pokes you in the arm with her silicon fairy wand, you’re no longer certain.  “What … are you?,” you ask.

            “I’m the Cornell CS fairy,” she responds.  “My job is to defend the CS department against the dark forces of evil.”

            “You mean, like the EE department?”

            “No, even more evil than that.  This semester the CS department has been infiltrated by a little-known visiting professor named Dr. Konrad Theoryborg.  He teaches a seminar called COMS666 Insanely Advanced Algorithms (prerequisite: immortality), which meets at 5:12 AM in a secret chamber underneath Upson.  I have reports that Dr. Theoryborg is plotting something sinister, and I need ACSU members like you to help me investigate.”

            (If you’re not an ACSU member, then you join now, by paying the $10 dues to the CS fairy.)

            Moved by your sense of duty as an ACSU member, you follow the CS fairy down into the basement.  There, she waves her silicon wand over the candy machine, magically causing it to rise and revealing a hidden tunnel underneath. 

 

Question 1

 

Following the CS fairy, you crawl through the narrow, serpentine tunnel, which seems to meander widely beneath the engineering quad.  Soon you come upon a side tunnel; after following this for perhaps a hundred yards, you find a lighted sign reading ‘0000000 0000000.’  And nothing else.  Returning to the main tunnel, you continue crawling until you find a second side tunnel; following it, you find a lighted sign reading ‘0000000 0000001.’  The third side tunnel leads to sign reading ‘1000000 0000000’; the fourth, to a sign reading ‘1000000 0000001’; and the fifth, to a sign again reading ‘1000000 0000001.’

            “The pattern,” says the CS fairy, “seems to be add 1 in binary, reverse the digits, add 1, reverse the digits, and so on.  My intelligence indicates that Dr. Theoryborg’s secret chamber is in the first side tunnel with a sign reading ‘1111001 1001110.’  It would be useful if you could figure out what the number of this side tunnel this is in the sequence, so that we don’t have to waste time crawling through every side tunnel we come across.”

 

Question 2

 

When you and the CS fairy finally reach Theoryborg’s secret chamber, you find that the COMS666 lecture has already commenced.  Seven students are huddled around the master, a wiry, intense-looking man who’s brandishing a glowing blue ellipsoid with a convex polyhedron transcribed in it.  “That,” whispers the CS fairy, “is Theoryborg’s terrifying Orb of Polynomiality.  It’s rumored that, with its power, Theoryborg can solve in polynomial time problems that have driven others mad with fright—some say even NP-complete ones.”

Meanwhile, a student is asking Theoryborg a question: “… But what if the edge weights are given in unary?”

“Then,” responds Theoryborg nonchalantly, “constructing a maximum-weight perfect matching actually turns out to be in random-NC.  That’s due to Karp, Upfal, and Wigderson in STOC’85, pages 22-32, and also independently to myself, in an unpublished manuscript written when I was fourteen months old.”

            Theoryborg pauses for a moment, to allow all assembled to venerate his perspicacity, then turns to you and the CS fairy.  “And do we have visitors today?”

            You introduce yourself.  “I don’t mean to interrupt,” you say, “but I was wondering whether you’re planning to take over the world or something.”

            “I do plan to take over the world,” Theoryborg responds with a snort, “if and only if the number of 2-state Turing machines that halt is divisible by eight.  A 2-state Turing machine, of course, looks like this”—he draws on the blackboard:

 

 

If on a ‘0’ square

If on a ‘1’ square

If in State 1 Write 0, move left, go to state 2 Write 0, move left, halt
If in State 2 Write 1, move right, go to state 1 Write 1, move left, go to state 2

 

            —“and it runs on a tape with squares extending infinitely both left and right.  Initially all the squares have ‘0’ on them, and the machine is in state 1.  The machine I drew, for example, has the following execution run”—he draws again:

 

~ ~ ~ State 1 ~
0 0 0

~ ~ State 2 ~ ~
0 0 0

~ ~ ~ State 1 ~
0 1 0

~ ~ State 2 ~ ~
0 1 0

~ State 2 ~ ~ ~
0 1 0

~ ~ State 1 ~ ~
1 1 0

~ Halt ~ ~ ~
1 0 0

 

“So,” continues Theoryborg, “for each of the four squares in the table, there are two choices for what to write (0 or 1), two choices for what direction to move in (left or right), and three choices for what state to go to (1, 2, or halt).  Therefore the number of possible machines is (2´2´3)4 = 20,736.  And the question is how many of those ever go into the halt state.  Here’s a hint: no machine runs for more than six steps before halting.”

“Enough idle pedantry!,” you interject.  “We’re on to your game, Theoryborg!”

“That’s unlikely,” Theoryborg deadpans, “since my game is provably PSPACE-complete under L-reductions.”

“Attack!,” shouts the fairy—but too late, for as Theoryborg rubs the Orb of Polynomiality his body becomes translucent and fades away, until nothing remains but his smirk.  “Office hours will be posted on the web!” announces the smirk, and then it too disappears.

The students glance around the chamber, dazed.  “Say,” says one of them, “I wonder how many of those 2-state machines do halt?”

 

Question 3

 

Five students in the class, Bo, Cay, Dale, Emily, and Freddy, introduce themselves to you and the CS fairy.

            “We’re all proud, dues-paying members of the ACSU,” they announce in unison.

            “That’s nice,” says the CS fairy.  “But what we really need to know is, what nefarious plot is Dr. Theoryborg concocting?  Do you have any clues?”

            “Come to think of it,” says Bo, “Dr. Theoryborg did mention something in class about using his Orb of Polynomiality to find optimal positions for a network of a satellites that will shower the Earth with mind-control rays, thereby rendering the entire human race the obsequious minions of complexity theorists.”

            “At the time,” Bo adds, “I didn’t think much of it.  But as I look back, it does seem rather nefarious.”

            “How can we ever stop him?,” implores Dale.  “His IQ is greater than the product of all of ours!”

            “I have an idea,” says Cay.  “We five students, mortals that we are, are usually the slackers in COMS666.  So Theoryborg starts out every class by asking us five if we finished our problem sets.  He mockingly claims that he’ll be satisfied if the set of us who did has a subset whose names sum to nine letters long—that is, if it contains one or more of {Bo, Cay, Dale}, {Dale, Emily}, and {Cay, Freddy} as a subset.”

            “Call a set of us Borgian if it has that property,” suggests Freddy.  “For example, {Bo, Cay, Freddy} is Borgian, but {Bo, Cay, Emily} is not.”

            “So,” continues Cay, “let’s each of us flip a coin to decide whether we’ll complete tomorrow’s problem set, so that we each have an independent, 0.5 probability of doing so.  Then, in tomorrow’s class, we’ll tell Theoryborg about our coin-flipping strategy, but not about whether the coins landed head or tails.  Then we’ll beseech Theoryborg to ask us, one by one, in any order he chooses, whether we finished our problem sets.  The challenge for him will be to find an order that minimizes the mean number of questions until he knows for certain whether the set of us who finished their problem sets is Borgian.  The mean, of course, is over the 25 = 32 possible outcomes of our coin flips.”

            “It goes without saying that Theoryborg will find an optimal order,” says Emily.  “But I have a question: can Theoryborg change the order midway through, based on whether the answers are yes or no?”

            “Definitely not,” replies Cay.  “We’ll make him specify the order in advance.”

            “I see,” says Bo.  “So for example, if the set of us who finished the problems is {Bo, Emily, Freddy}, and if the questioning order that Theoryborg chooses is Dale®Emily®Cay®Freddy®Bo, then Theoryborg will know after exactly three questions that the set of us who finished the problems is not Borgian.”

            “Because,” says Emily, “he’ll know after three questions that Dale and Cay didn’t finish the problems, and no set of us containing neither Dale nor Cay can possibly be Borgian.”

            “My plan is brilliant!,” Cay beams to you.  “This whole questioning process will create a diversion, during which you and the CS fairy can steal the Orb of Polynomiality, thereby rendering Theoryborg powerless!”

            “But how long will we have?,” asks the CS fairy.  “I mean, what is the mean number of questions that Theoryborg will need to ask, multiplied by 10,000?”

            “Why multiplied by 10,000?” you ask, rather puzzled.

            “Oh, because the programming contest rules specify that the answer to each question has to be an integer.”

            “What programming contest?”

 

Question 4

 

Eleven hours later.  One hundred and thirty-one members show up for your emergency ACSU meeting, lured by the free pizza and by the prospect of saving the human race from eternal enslavement.  You deliver a speech to them that concludes with this rousing peroration—

            “And so at 5:12 tomorrow morning, in the dark tunnels beneath Upson Hall, we the proud, the brave, the ACSU shall form an invincible army that will wrest the gruesome Orb of Polynomiality from Professor Theoryborg.  We will not descend into the ghastly algorithmic night—for it is our destiny to prevail, to make the world safe for systems, safe for AI, safe for all the noble and all the righteous subdisciplines of CS.”

 

            “Thanks,” says the CS fairy.  “At this point we’ll open the floor to questions.”

            A hand shoots up.  “How is this, uh, army going to be organized?”

            “Good question,” you respond.  “As you know, each of you has been rated on a scale of 1 to 20 (20 being highest) on each of two criteria—warrior skill and CodeWarrior skill.  Remarkably, it’s turned out that for all ordered pairs of integers (x,y) with 1 £ x £ 20 and 1 £ y £ 20, there’s one of you with warrior skill x and CodeWarrior skill y if and only if 30cos(xy) > x + sqrt(y).  Also, no two of you have both the same warrior skill and the same CodeWarrior skill.”

            “Now,” continues the CS fairy, “we say that another person dominates you if that person’s warrior skill and CodeWarrior skill are both at least as great as yours—from which it follows, of course, that one of their two skills must be strictly greater than yours.  Also, we say that A is a commander of B if A dominates B and there’s no person C such that A dominates C and C dominates B.”

            “In other words,” you add, “if there’s no person who comes between A and B in the dominance hierarchy. Of course a person can have more than one commander, and can be the commander of more than one person.”

            “Right.  Now listen up: each pair of people (A,B) such that A is a commander of B will need to meet for a half-hour-long, one-on-one training session.”

            Another hand shoots up.  “But we don’t have much time.  How many of these training sessions will we need to hold?”

 

Question 5

 
The next morning, the trained ACSU soldiers storm the tunnels beneath Upson, wielding backlit PalmPilots as torches.  To your great trepidation, you and the CS fairy are in front.  When at last you reach the COMS666 chamber, you find that Bo, Cay, Dale, Emily, and Freddy’s diversion is working perfectly to plan: Theoryborg has left the Orb of Polynomiality on his desk while he interrogates the five students about their problem sets.  Racing into the chamber, you seize the Orb.  Twenty-five ACSU soldiers (for that’s as many as will fit) flood into the chamber and form an impenetrable barrier around you.  The chamber door slams shut.
“Not so fast,” Theoryborg demurs.  “In fact, O of square root of whatever your speed function was before.”

            “But without the Orb,” taunts the CS fairy, “there’s no way you can find optimal positions for your mind-control satellites and thereby enslave the human race.  The problem is just too hard for you.”

            Theoryborg smirks.  “Actually the problem is pretty trivial, because you see, I have a contingency plan.  I’ve pre-programmed one of my satellites to shoot mind-control rays directly into this chamber.  Here’s how it works: you’re #2, that stupid fairy is #3, and the twenty-five ACSU soldiers are #4 through #28.  When the satellite shoots a ray at person #N, it enslaves not only that person but also each person #M such that N and M are not relatively prime (that is, have a common factor at least 2).  And the satellite can shoot just enough rays to enslave all twenty-seven of you—at which point you’ll willingly return the Orb to me!”

            “How many rays can it shoot?,” inquires an ACSU soldier.

            Theoryborg tells you.

                The CS fairy laughs.  “That’s not enough.  You’re wrong, Theoryborg, wrong!”

            “Really?,” you ask.  “What is the minimum number of rays that would be required?”

 

Conclusion

 

“A—perfectly—well-defined—math—problem—and—my—answer—was—incorrect!”  Theoryborg howls with terror.  “Forgive me, Zermelo-Fraenkel axioms—forgive me, for I have sinned!”

            A drop of brown liquid descends from Theoryborg’s finger—then two drops, then four, then eight, then sixteen.  At an exponential rate, Theoryborg melts into a puddle of Coke on the floor.  The ACSU soldiers rejoice, for no longer will this algorithmic evildoer menace the Earth.

 

You awake to the humming of NT boxes in the CSUGLAB.  It’s 5:05 AM on Monday morning.  Were the CS fairy, and Dr. Theoryborg, and all your adventures but a dream?  With a tinge of regret, you compile your Java program one more time.  And miraculously, it works!

[Return to Writings page]