The ACSU Versus the Evil
Professor Theoryborg: A Tale of High Adventure and Low Address Bits
by Scott
Aaronson
March
4, 2000
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.
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.
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.”
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?”
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?”
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?”
“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?”
“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!