"Andrew Burt - Fiction You Bet Your Planet" - читать интересную книгу автора (Burt Andrew)

E-scape--Fiction: You Bet Your Planet

You Bet Your Planet

by Andrew Burt

      "I win that black box or you take over the Earth?" Professor Forster Templeton's hand shook as he smoothed back his thinning hair. He blinked rapidly, but the aliens were still there. He sniffed: They still smelled like burnt hair. "Don't get me wrong. I'd give an ear to know how that box does what you say. To speed up our slowest algorithms would revolutionize whole industries; it could topple governments." He shrank back into his leather chair. "No, the risk is too great. I'm…I'm not a gambling man." Also quite delusional, he thought to himself. He blinked again.
      The first alien—Hutheefushee, it had introduced itself—tapped its slim tentacles impatiently on all of its six stump-like legs, looking like a round, bar-stool-sized elephant overgrown by ivy. It dripped slime onto the professor's neat piles of student project reports that he'd meant to read last semester but assigned grades for anyway. The second alien, Yoongopoth, cradled a small black box and studied the books in the well-appointed and comfortable, but cramped office. Its thirty-six eyes roamed, independently, up and down the books stacked on the handsome mahogany shelves; each matching vocalizer hummed in what might be approval at the well-worn spines of Knuth's multi-volume "The Art of Computer Programming," or clucked in what might be disapproval at the library's inclusion of Bill Gates' autobiography.
      "But you are the best suited to accept the wager!" Hutheefushee answered his objection, the ribs of each speech organ vibrating out one word apiece like plucked rubber bands, sending spittle machine-gunning in a circle around the room. (Or at least Forster thought of it as spittle. Best not to think too hard on it, he decided, brushing away the wet droplets from his arm with a handkerchief.) "You are the humans' foremost authority on—" Hutheefushee began.
      "Computational complexity," one of Yoongopoth's ribbed organs added, filling in apparently troublesome key words—
      "—are you not?" Hutheefushee finished. "You know the mathematical limits of computer abilities like no other human. The Templeton lemma, theorem, algorithm, and speculation—"
      "Conjecture," corrected Yoongopoth.
      "—bear your name, yes?"
      Forster flushed modestly. "Other people have theorems and conjectures named after them too," he protested. "I admit it's a tempting challenge, but the fire in my belly to be a household name isn't even an ember. Besides, I haven't published in years," he lied, hoping they would forget the wager. Perhaps in the foolhardiness of youth he might have risked the Earth on a point of theory, but he was more cautious now. 'Cautious,' he secretly knew, meant 'run from a challenge to avoid failure,' and he cast his eyes downward. "No, gentlem—er, beings, I'm washed up. Sorry. There's nobody to take your bet. If you'd come twenty years ago…"
      "Then we will visit Ramanathan or Tong or Miller. She or he or he are dim to your brilliance. In your future histories, your name will stand beside…"
      "Gцdel and Turing," Yoongopoth continued.
      "…not theirs. Though if you decline, we must offer one of them the wager instead. But," Hutheefushee said, tapping the cherrywood, Hammacher-Schlemmer replica-antique globe beside the desk once owned by Thomas Jefferson, "do you entrust your planet to them?"
      Forster grimaced as Hutheefushee dripped slime on the globe and its gold-plated meridian. Meredith had given it to him almost a decade ago, on their twenty-fifth wedding anniversary—a year before she'd called him a spineless wimp and run off with the pool boy. He kept the globe as a reminder of the fallibility of the perfect, yet he'd hardly noticed its presence in ages. He reconsidered his abilities. Could he save the world? No, computer science was a game for the young. Like the pool boy. Forster felt his sixty years.
      "I suppose I have to trust them." Especially since I'm the one hallucinating, he thought. "But I'm curious, what if they also refuse your terms?"
      "Ah, that is most unlikely. Even if the probability that any one human would accept were ridiculously small, the probability of some human accepting—"
      "Not all humans not accepting," elaborated Yoongopoth.
      "—is essentially one point zero. Some one of your billions will take our wager, even if they are mathematically ignorant. Suit yourself, Dr. Templeton. It's your planet at risk."
      They turned as if to leave, though Forster had a hard time telling their side or back from their front, and merely guessed at their intent. He remembered Meredith turning away from him in disgust, the pool boy in his van out front, waving her to come on. What had she seen in him?
      "Wait, wait, wait," he implored, the leather creaking as he rose from his chair. They stopped. He sat back, slowly, contemplating the risks. If he was still the best—and despite his modesty, in his heart he prayed it was so—then to decline would risk the enslavement of humanity on his fear of failure. "Of course, I have no choice," he said at last. "If nobody accepts—which, as you say, is highly improbable—you'd no doubt take what you want anyway."
      They tittered—or so it sounded. "That is very prehensile—" Hutheefushee said.
      "Perceptive," Yoongopoth amended.
      "—of you. Because your species would have proved itself not intelligent, we would simply take your planet. Just as you humans take without remorse from your subordinate species, the…"
      "Ants. And dolphins and parrots and elephants and—"
      Hutheefushee shushed its companion with a wagging tentacle. "Who all failed this test," he continued with what might have been a stern look toward Yoongopoth. "But if you can solve this puzzle, then you are an intelligent race and we will put aside our plans."
      "Plans?" Forster asked with trepidation.
      "Yoongopoth hopes to organize safari hunts with molecular disrupters, though I prefer the gladiatorial games. But if you are intelligent then it would be…"
      "Rude."
      "…and we would not presume to interfere with your world. We are, after all, a civilized race. So. It is settled? You accept?"
      Forster rubbed his face with both hands. If he were crazy, what could it hurt? Maybe his subconscious was telling him he'd found a breakthrough in theory. Maybe that fire in the belly was still an ember. And if he were sane, could he survive the guilt of enslaving humanity? With a grimace and roll of his eyes, he said "God help me. I accept."
      "Excellent!" Hutheefushee proclaimed with a flourish of his many tentacles. "In here, as I explained" it said, tentacling over the black box, "is a program to solve what you call the Traveling Salesperson Problem: It finds the fastest path among all of a network of locations with varying travel times between various pairs."
      "For which," Forster explained in his teaching voice, "just so you understand correctly, the only solutions we humans know take exponentially longer with a linear increase in input size, making it computationally impractical to solve for large inputs."
      "Yes, yes! This box is much faster! It can handle any size input very quickly."
      "Incredible. That would imply that P equals NP!" he muttered, referring to the most famous computational question as yet unanswered by the best computer scientists of the age: whether a set of certain very hard problems, called NP, had efficient solutions, called P. Some suspected it might be true, but that humans had yet to develop the theory necessary to prove it. Others were as sure it was false. A few thought it might be both simultaneously. "And you're sure you're using our same model of 'computation'?"
      "The box has inside it what you call a Turing machine, after your distinguished Alan Turing, who defined your concept of computability. Thus, it—"
      "That's impossible!" Forster burst in. "A Turing machine, by definition, must have an infinite amount of memory! You can't actually build one."
      The pair tittered again. "No! Yes! It has a tame dark pit—" Hutheefushee started.
      "Harnessed black hole," Yoongopoth interrupted.
      "—inside, both for storage and power. You must not open it!"
      "No! No! Very dangerous," Yoongopoth added for emphasis.
      "Here, let us show you proper operation," Hutheefushee said, before explaining the workings of the box: how to get help and how to use the vocal input/output mode, the holographic pointing and display modes, and a mode adapted for direct linkage to Earth-style computers—at the mention of which both aliens shuddered as if in disgust at its primitive use of metal wires. "The…"
      "Telepathy mode."
      "…has been disabled. For your protection, of course. As a hint, we suggest you look at the order of the output. To save time, you may describe the locations you wish to test; the box can determine the coordinates of all locations on your planet. So." Both aliens fluttered their tentacles like a horse tossing its mane. "We will return in one planetary orbit," Hutheefushee said.
      "Year," clarified Yoongopoth.
      "At that time, you will tell us the algorithm in this box. Remember, you must work alone; the box will be watching and your planet is forfeit. Solve the puzzle, keep the box. Otherwise, the planet and its life forms are ours. Good bye."
      The pair winked out, leaving Forster alone with the dreadfully important black box.

      "Thank you, thank you. You may go."
      The boy dashed out.
      Forster wiped his brow. It was real. At least, he thought it was real. If he were imagining this too… No, mustn't think like that. He pounded the antique desk. The box was real, and he had a life's work to complete in a year.
      So many ways to tackle the problem. He sighed, sitting heavily into his chair. Perhaps he should try a little of each approach, see what worked best. Or should he exercise on path to exhaustion first? His work habits had become so sloppy, he mused. Must work on that.
      Forster paused momentarily, reflecting. He'd become sloppy and timid in all aspects of his life. In an instant's insight, he understood why Meredith had left him. If only it were ten years ago. Forster shook off his reminiscence and plunged into his work.
      Day after day, weekends after weekdays, Forster unlocked the computer sciences building before dawn, and until well after dark light from his window cast shadows on campus. He missed classes frequently and when he didn't, he rambled, unprepared and bleary eyed. He often digressed about Turing machines and intractable problems, questioned whether "fast" solutions existed for traveling salespeople, mumbled about Hamiltonian circuits when the syllabus showed "regular expressions," and waxed philosophical about determinism—always receiving the same output for the same input, he explained—and problems with deterministic or non-deterministic polynomial time solutions, invoking their sacred names of P and NP months ahead of schedule or in the wrong class altogether.
      Greenstein, the department chairman, inquired to his heath. Forster, his sweat-stained shirt half untucked, waved him off with a mumble about a breakthrough that would make Nobel prizes look insignificant. Greenstein went away with a smile.
      Few students visited Forster's office hours more than once, for they would find him ignoring their presence—and their questions—as he feverishly tapped on his keyboard and waved his hands over the strange black box to which his workstation was connected.
      Forster found that the box's intelligence could accurately determine the distances between cities with no more than a description of the desired travels, allowing him to rapidly enter datasets of all sizes and compositions. Should such roads have been built, civilization would be smothered under the deluge of asphalt. Holographic solutions appeared before the box instantaneously no matter how large the input, attesting to its immense speed, but preventing validation of the aliens assertion that it solved problems efficiently: A problem of one size input took no measurable time to be solved, making it impossible to determine if twice as much data took four times as long, or nine, or sixteen. Forster grudgingly accepted their assertion on faith. The planet hung in the balance. He could do this, he reassured himself.
      Forster told his teaching assistants to take all his classes. He locked his door. Month after month he poured over printouts of runs, analyzing their order as the aliens had hinted. He compared outputs with slight variations in input. He built conjectures, tested them—and just when one appeared promising, a contradictory case appeared, and he could prove the algorithm would have to run in exponential time like any ordinary human algorithm. Forster skipped meals. When hunger struck, unwilling to leave the enslaving black box, he ordered delivered the very kinds of food he loathed: pizza, Chinese, and Italian. He smiled at, but otherwise forced himself to ignore the flirtations of the handsome, middle-aged woman who brought the calzones. He began sleeping in the office, at first on the leather couch, then yielding to slumber while seated at his desk. When the last of the overhead lights winked out, he worked by the glow of the screen.
      He wore himself out.
      Sniffling and congested from a chronic stress cold, Forster slouched, unmoving, in the back of a taxi he'd hired so he could pick up more decongestants at the pharmacy. He checked his watch again. A mere two hours until the aliens returned. He sighed. Perhaps it was an impossible task. Perhaps he should have let Ramanathan do it. Either way, he'd failed. The best he could do was to resolve to face them without the indignity of a runny nose. He wallowed in self-pity, imagining himself speaking with the President and the Secretary-General of the United Nations. "I'm sorry madam, sir, but I seem to have lost the Earth on a bet. Humans apparently aren't intelligent enough, you see. I know I should have informed you long ago, but—"
      The solution appeared in his mind. "Long ago," that was it!
      "Quick, driver! Back to the campus, immediately!"
      It had always bothered him that the box could produce the answers so rapidly that he was unable to verify the polynomial running time they claimed. He'd been so concerned with the upper bound on how long it took, whether it could finish larger tasks in polynomial time, that he'd failed to consider the lower bound: That it did them, in fact, too rapidly.
      Forster was half out the taxi before it stopped. He flung a wad of twenties at the driver and loped unsteadily toward his office, where he waved up the help information from the box. "Box, can you generate randomized input for yourself?"
      "So long as it contains a finite number of locations within the magnetosphere of your planet—of course."
      "And you can do that in linear time? For any size dataset?"
      "With my infinite memory, I can generate and operate on any finite number of points more rapidly than you can describe them. I could even verify them by repetition, if you wish," it seemed to sniff, as if hurt at his lack of appreciation for the box's sophistication.
      "Then please create random datasets and operate on them, doubling the size of the input, until the elapsed run time for a dataset exceeds one second."
      Forster sat into his favorite leather chair, head back, taking a deep snuffly breath to smell its rich, relaxing aroma. He steepled his fingers. Given that the algorithm's purported growth rate—being polynomial—was slower than the exponential growth of the size of the dataset, it should quickly reach a dataset that would exceed one second of time. In fact, the slowest it could ramp up to a full second was if the algorithm was also linear (and thus having to look at each item of data merely once). Forster knew, like a preacher knows his Psalms, that the sum of powers of two is always only one less than the next power of two: The box should reach the one-second limit in no more than one second.
      It had been a minute.
      The box was faster than theoretically possible.
      The box was a fake.
      Forster rocked in his chair and waited, a satisfied grin below his watery eyes.
      Hutheefushee and Yoongopoth blinked in, on schedule, their tentacles all aquiver. The box was still running, still having failed to produce a computation exceeding a second, despite that the input had continued to double in size astronomically.
      "Your box is a charlatan," he said, blowing his nose and feeling grateful he couldn't smell the aroma of burnt hair. "A fake! It runs faster than linear time. It runs so fast, it has no time to look at every data element. It can't be deterministic. There is no such algorithm. I win."
      Hutheefushee and Yoongopoth rotated toward each other like intertwined cogs, then back. They tittered. "We're afraid you are…"
      "Mistaken."
      "…we never said it was…"
      "Deterministic."
      "Only 'fast.' You drew conclusions; we did not confirm."
      Forster thought back. "You said it had a Turing machine inside."
      "But it contains other elements as well. The wager was on the algorithm. Have you understood it?"
      "There can be no such algorithm, that's what I'm telling you! It's a cheat!"
      Yoongopoth's vocalizers made what sounded like a sigh. Hutheefushee spoke. "You disappoint us. We admit the box enters a time loop that returns to the time of input after the Turing machine has computed the result—which it does in ordinary, exponential time, inside the time loop. But that was not the wager. If you do not understand the algorithm, then we win."
      Hutheefushee rested slimy tentacles on the Hammacher-Schlemmer globe.
      Forster hung his head. He'd tried so hard to see the alien trees that he'd missed the obvious, that there was no alien forest. Perhaps one of the algorithms he'd thrown out as too slow had been correct. He thrust his palms out, imploringly. "But…"
      Hutheefushee tentacled the black box off Forster's desk and rested it atop the globe. "Thank you for a very enjoyable wager," it said, laying an ordinary piece of paper before the professor. "Deed to planet Earth," the sheet read. "Sign here, here, and here, below the ants" the alien said, dripping slime onto the Jeffersonian desk as it pointed. Another tentacle offered him a pen.
      Forster wiped his feverish forehead, thinking sardonically that at least he didn't have to worry about the pool boy any more. Perhaps they'd bag him as game on one of their safaris.
      Forster suddenly straightened. "Double or nothing?" he asked. "I'll bet you the rest of our solar system if your box can solve one last problem. I think I know some data it can't handle."
      Hutheefushee shivered as if in excitement. "The data are all locations—"
      "Places," Yoongopoth clarified.
      "—on Earth? Cannot be infinite," Hutheefushee scolded.
      "Absolutely. But one condition," Forster said, wagging a finger. "Since this data set is complex, you must agree to wait for the box to display the results and run the data again until it obtains the same solution twice."
      "Of course it will get same results twice," Hutheefushee exclaimed with what might have been glee. "Agreed!"
      Forster straightened his shirt and cleared his throat. "Box, for the following data, please repeatedly calculate and holographically display the results until two consecutive runs are identical. Do you understand?"
      "Of course. Enter your data."
      "Observing Hutheefushee and Yoongopoth here, please find the shortest path among all the electrons in their bodies. Begin."
      Eerie shadows of the box, the globe it rested on, Forster, and the aliens began dancing on the walls. The holographic projections of the two aliens pulsated white-hot while solution paths flashed like lightning at midnight as fast as the box could drain its black hole. Forster wiped a trickle of sweat from his fevered forehead.
      Forster smiled. Meredith would be proud of him now.
      Hutheefushee took a step back and thrust out several tentacles as if shielding itself from attack. "Why has it not finished?" Hutheefushee demanded, pivoting toward Yoongopoth. "It computes instantly!" The aliens shuddered like dishes during an earthquake and squealed and squawked in what Forster suspected might be a heated argument in their normal tongue. The point on the globe nearest the holograms began to darken and peel back and a wisp of smoke curled upward.
      "Excuse me, but don't you understand your own box?" Forster interrupted. "It can't finish. Although time effectively stops while the box enters the time loop to compute paths between your electrons, it takes a brief moment of real time to display the results. When it's ready to compute again, your electrons have moved. No two solutions can ever be the same. And don't forget, if your electrons leave the planet, you lose the bet. You agreed." Forster folded his arms. "You're trapped here."
      "Electrons aren't cities," Hutheefushee said, matter-of-factly. "Illegal data. We win."
      "No, you said, specifically, locations," Forster countered.
      "You've tricked us!" Yoongopoth cried out. "We will have to wait here forever to not lose the bet!"
      The Hammacher-Schlemmer globe suddenly burst into flames beneath the box.
      "Well, not exactly here," Forster said, waving futilely at the cloud of malodorous smoke. The buzz of the building's fire alarm rent the air like the second coming.
      "You've broken the box!" Hutheefushee cried.
      Forster considered. "No, it's just the photons from the displays." The overhead sprinkler suddenly spewed water at Forster, the aliens, Bill Gates's autobiography, Jefferson's desk, the unread student papers, and the inferno of the box; the water hissed and sizzled like bacon as it lost its battle with the box. The room fogged up with steam.
      "Exponential heat! The time loops!" Yoongopoth said, backing away.
      "The dark pit! Melt!" Hutheefushee said, backing away.
      In his feverish haze, Forster imagined the water melting them like a certain wicked witch, then realized they meant the heat output from the black hole was too rapid. "Serves you right!" he shouted. "Wait a minute, how big is the black hole? What will melt?"
      "Crisp whole planet!" Hutheefushee said. "Bad trick, very bad! Bad human!"
      Forster swallowed hard. He'd only meant to trap them logically, stall the bet for eternity or until they gave up, but being a theorist, he'd forgotten there might be physical effects to his algorithm. He could stop the box. Forster opened his mouth, remembered Meredith calling him a spineless wimp, and closed it. Forster rose and threw his head back into the sauna-like spray. He smoothed his hair as if it were a refreshing shower. "Feels like being hunted on a safari, doesn't it, Hutheefushee? God, what a paper this would make!" he shouted over the fire alarm, feeling two sorts of heat in his belly. Indeed, three: Hyped on adrenaline, he pictured himself sweeping that flirtatious Italian delivery woman off her feet if he survived.
      Thomas Jefferson's desk erupted into flames. Thick smoke began to fill the room.
      Forster knew he should leave to save his life. Instead, he advanced on the aliens, hands on hips. "Forfeit the double-or-nothing or die, you cowards!"
      The aliens heaved and grunted simultaneously. "Bah!" said Hutheefushee. "Humans!" said Yoongopoth. Fire raced across the student papers toward the aliens. Bill Gates' and Knuth's names blackened and peeled from their books. Hutheefushee waved his tentacles dismissively. "Very well, very well, you win your 'nothing.' But this doesn't prove your race is intelligent."
      "Don't bet on it!" Forster shouted, waving a fist, but the aliens and the box had blinked out, never to be seen again.

Publishing Co. All rights reserved.

E-scape--Fiction: You Bet Your Planet

You Bet Your Planet

      The problem, Forster soon realized, was that with only a year to work, and so many possible approaches to the solution, he had to solve the problem in order to solve the problem: Some path through the various possible approaches was the shortest, and touched on every element of the solution that he would need, but he didn't know what that path was—the Traveling Salesperson Problem itself, in miniature. It made it almost unbearable to know, by definition, that there was a solution. It was much easier to ignore such queasiness when nobody knew if it could even be solved.
      The first step, though was clear: To verify he wasn't crazy. But how to do that… He picked up the phone to call Ramanathan. He put it down. Aliens? Black holes? She wouldn't believe him. The FBI, then? No. They weren't technically competent to understand the problem. The CIA? Not their jurisdiction. The National Security Agency, renowned as much for their brilliance with cracking codes as for their secrecy? This was a code of sorts, figuring out how it produced its outputs for a certain set of inputs. Yes, they would believe him. He looked up their number.
      Only… He reconsidered as it rang. They would take the box away, and do Lord knows what with him. If it did what he claimed then that would authenticate where he claimed it was from. Especially with alien spittle and slime all over his office to boot. The government wouldn't tolerate proof of aliens floating around, notwithstanding exciting proofs about P and NP. At the very least, they'd want to dissect the box and inspect it for tentacle prints. There was also that nasty threat about not doing it alone. "National Security Agency," a voice said. He hung up.
      Any publicity would have the same effect, he decided. Word gets around. Even if he didn't say where it came from, people would ask questions. It would have to be someone who didn't understand the problem. Nor would that count as 'working' with someone, he rationalized.
      He jogged to his office door, opening it to the bustle of students beyond. "You there," he beckoned to a bug-eyed youth. Probably a freshman, Forster thought, though it had been how long since he'd taught an undergraduate level class? He pushed the thought aside. "Come here, quickly."
      The boy hesitantly entered the plush office, holding tightly to his backpack's strap. "Yes, sir?"
      "Your major, son, what is it?"
      "Anthropology, sir."
      "Good, good. Know anything about computers?"
      "Very little, professor. I was here to take a course on word processing. We have to type—"
      "Excellent!" he said, adding with a wink, "I mustn't be accused of cheating, you know." Forster waved his hand over the box as Hutheefushee had shown him to enable vocal input mode. "Tell me, where are you from?"
      "Los Angeles."
      "And how many miles is it from there to Boston?"
      The boy's eyes widened in fear at the sudden geography quiz. "I…"
      "Just guess! Approximately!"
      "Three thousand miles?"
      "Fine. How far from—wait. Here." Forster dug around in his shelves for a road atlas. "Pick four more random cities and read the number of miles between all of them."
      "Uhhh," the boy paused, eyeing that the mad professor stood between him and the door. "Uh, sure. From Atlanta to Boston is 1,037 miles, from…" and he read in a small network of cities.
      "Good, that's enough. Device," he addressed the box, "what is the shortest path?"
      "Denver to St. Louis, St. Louis to Boston, LA to Denver…"
      Forster jotted down the list, in what seemed a random order as the machine spoke.
      "Now, son, look at this very carefully." Forster showed him a quick sketch of the cities and distances he'd read in, with the box's path highlighted. If you drove this, do you see any shorter way to travel and go to each city? Here's a calculator."
      The boy eyed the door again, then the map. He chewed on his lip. He added some sums on Forster's calculator. "No, um, professor, I don't. Can I go now?" he asked, biting his lip.
      "Wonderful! Now, please write down your name, the date, and that you witnessed this box producing this answer."
      After a brief hesitation, the boy complied.
      "Thank you, thank you. You may go."
      The boy dashed out.
      Forster wiped his brow. It was real. At least, he thought it was real. If he were imagining this too… No, mustn't think like that. He pounded the antique desk. The box was real, and he had a life's work to complete in a year.
      So many ways to tackle the problem. He sighed, sitting heavily into his chair. Perhaps he should try a little of each approach, see what worked best. Or should he exercise on path to exhaustion first? His work habits had become so sloppy, he mused. Must work on that.
      Forster paused momentarily, reflecting. He'd become sloppy and timid in all aspects of his life. In an instant's insight, he understood why Meredith had left him. If only it were ten years ago. Forster shook off his reminiscence and plunged into his work.
      Day after day, weekends after weekdays, Forster unlocked the computer sciences building before dawn, and until well after dark light from his window cast shadows on campus. He missed classes frequently and when he didn't, he rambled, unprepared and bleary eyed. He often digressed about Turing machines and intractable problems, questioned whether "fast" solutions existed for traveling salespeople, mumbled about Hamiltonian circuits when the syllabus showed "regular expressions," and waxed philosophical about determinism—always receiving the same output for the same input, he explained—and problems with deterministic or non-deterministic polynomial time solutions, invoking their sacred names of P and NP months ahead of schedule or in the wrong class altogether.
      Greenstein, the department chairman, inquired to his heath. Forster, his sweat-stained shirt half untucked, waved him off with a mumble about a breakthrough that would make Nobel prizes look insignificant. Greenstein went away with a smile.
      Few students visited Forster's office hours more than once, for they would find him ignoring their presence—and their questions—as he feverishly tapped on his keyboard and waved his hands over the strange black box to which his workstation was connected.
      Forster found that the box's intelligence could accurately determine the distances between cities with no more than a description of the desired travels, allowing him to rapidly enter datasets of all sizes and compositions. Should such roads have been built, civilization would be smothered under the deluge of asphalt. Holographic solutions appeared before the box instantaneously no matter how large the input, attesting to its immense speed, but preventing validation of the aliens assertion that it solved problems efficiently: A problem of one size input took no measurable time to be solved, making it impossible to determine if twice as much data took four times as long, or nine, or sixteen. Forster grudgingly accepted their assertion on faith. The planet hung in the balance. He could do this, he reassured himself.
      Forster told his teaching assistants to take all his classes. He locked his door. Month after month he poured over printouts of runs, analyzing their order as the aliens had hinted. He compared outputs with slight variations in input. He built conjectures, tested them—and just when one appeared promising, a contradictory case appeared, and he could prove the algorithm would have to run in exponential time like any ordinary human algorithm. Forster skipped meals. When hunger struck, unwilling to leave the enslaving black box, he ordered delivered the very kinds of food he loathed: pizza, Chinese, and Italian. He smiled at, but otherwise forced himself to ignore the flirtations of the handsome, middle-aged woman who brought the calzones. He began sleeping in the office, at first on the leather couch, then yielding to slumber while seated at his desk. When the last of the overhead lights winked out, he worked by the glow of the screen.
      He wore himself out.
      Sniffling and congested from a chronic stress cold, Forster slouched, unmoving, in the back of a taxi he'd hired so he could pick up more decongestants at the pharmacy. He checked his watch again. A mere two hours until the aliens returned. He sighed. Perhaps it was an impossible task. Perhaps he should have let Ramanathan do it. Either way, he'd failed. The best he could do was to resolve to face them without the indignity of a runny nose. He wallowed in self-pity, imagining himself speaking with the President and the Secretary-General of the United Nations. "I'm sorry madam, sir, but I seem to have lost the Earth on a bet. Humans apparently aren't intelligent enough, you see. I know I should have informed you long ago, but—"
      The solution appeared in his mind. "Long ago," that was it!
      "Quick, driver! Back to the campus, immediately!"
      It had always bothered him that the box could produce the answers so rapidly that he was unable to verify the polynomial running time they claimed. He'd been so concerned with the upper bound on how long it took, whether it could finish larger tasks in polynomial time, that he'd failed to consider the lower bound: That it did them, in fact, too rapidly.
      Forster was half out the taxi before it stopped. He flung a wad of twenties at the driver and loped unsteadily toward his office, where he waved up the help information from the box. "Box, can you generate randomized input for yourself?"
      "So long as it contains a finite number of locations within the magnetosphere of your planet—of course."
      "And you can do that in linear time? For any size dataset?"
      "With my infinite memory, I can generate and operate on any finite number of points more rapidly than you can describe them. I could even verify them by repetition, if you wish," it seemed to sniff, as if hurt at his lack of appreciation for the box's sophistication.
      "Then please create random datasets and operate on them, doubling the size of the input, until the elapsed run time for a dataset exceeds one second."
      Forster sat into his favorite leather chair, head back, taking a deep snuffly breath to smell its rich, relaxing aroma. He steepled his fingers. Given that the algorithm's purported growth rate—being polynomial—was slower than the exponential growth of the size of the dataset, it should quickly reach a dataset that would exceed one second of time. In fact, the slowest it could ramp up to a full second was if the algorithm was also linear (and thus having to look at each item of data merely once). Forster knew, like a preacher knows his Psalms, that the sum of powers of two is always only one less than the next power of two: The box should reach the one-second limit in no more than one second.
      It had been a minute.
      The box was faster than theoretically possible.
      The box was a fake.
      Forster rocked in his chair and waited, a satisfied grin below his watery eyes.
      Hutheefushee and Yoongopoth blinked in, on schedule, their tentacles all aquiver. The box was still running, still having failed to produce a computation exceeding a second, despite that the input had continued to double in size astronomically.
      "Your box is a charlatan," he said, blowing his nose and feeling grateful he couldn't smell the aroma of burnt hair. "A fake! It runs faster than linear time. It runs so fast, it has no time to look at every data element. It can't be deterministic. There is no such algorithm. I win."
      Hutheefushee and Yoongopoth rotated toward each other like intertwined cogs, then back. They tittered. "We're afraid you are…"
      "Mistaken."
      "…we never said it was…"
      "Deterministic."
      "Only 'fast.' You drew conclusions; we did not confirm."
      Forster thought back. "You said it had a Turing machine inside."
      "But it contains other elements as well. The wager was on the algorithm. Have you understood it?"
      "There can be no such algorithm, that's what I'm telling you! It's a cheat!"
      Yoongopoth's vocalizers made what sounded like a sigh. Hutheefushee spoke. "You disappoint us. We admit the box enters a time loop that returns to the time of input after the Turing machine has computed the result—which it does in ordinary, exponential time, inside the time loop. But that was not the wager. If you do not understand the algorithm, then we win."
      Hutheefushee rested slimy tentacles on the Hammacher-Schlemmer globe.
      Forster hung his head. He'd tried so hard to see the alien trees that he'd missed the obvious, that there was no alien forest. Perhaps one of the algorithms he'd thrown out as too slow had been correct. He thrust his palms out, imploringly. "But…"
      Hutheefushee tentacled the black box off Forster's desk and rested it atop the globe. "Thank you for a very enjoyable wager," it said, laying an ordinary piece of paper before the professor. "Deed to planet Earth," the sheet read. "Sign here, here, and here, below the ants" the alien said, dripping slime onto the Jeffersonian desk as it pointed. Another tentacle offered him a pen.
      Forster wiped his feverish forehead, thinking sardonically that at least he didn't have to worry about the pool boy any more. Perhaps they'd bag him as game on one of their safaris.
      Forster suddenly straightened. "Double or nothing?" he asked. "I'll bet you the rest of our solar system if your box can solve one last problem. I think I know some data it can't handle."
      Hutheefushee shivered as if in excitement. "The data are all locations—"
      "Places," Yoongopoth clarified.
      "—on Earth? Cannot be infinite," Hutheefushee scolded.
      "Absolutely. But one condition," Forster said, wagging a finger. "Since this data set is complex, you must agree to wait for the box to display the results and run the data again until it obtains the same solution twice."
      "Of course it will get same results twice," Hutheefushee exclaimed with what might have been glee. "Agreed!"
      Forster straightened his shirt and cleared his throat. "Box, for the following data, please repeatedly calculate and holographically display the results until two consecutive runs are identical. Do you understand?"
      "Of course. Enter your data."
      "Observing Hutheefushee and Yoongopoth here, please find the shortest path among all the electrons in their bodies. Begin."
      Eerie shadows of the box, the globe it rested on, Forster, and the aliens began dancing on the walls. The holographic projections of the two aliens pulsated white-hot while solution paths flashed like lightning at midnight as fast as the box could drain its black hole. Forster wiped a trickle of sweat from his fevered forehead.
      Forster smiled. Meredith would be proud of him now.
      Hutheefushee took a step back and thrust out several tentacles as if shielding itself from attack. "Why has it not finished?" Hutheefushee demanded, pivoting toward Yoongopoth. "It computes instantly!" The aliens shuddered like dishes during an earthquake and squealed and squawked in what Forster suspected might be a heated argument in their normal tongue. The point on the globe nearest the holograms began to darken and peel back and a wisp of smoke curled upward.
      "Excuse me, but don't you understand your own box?" Forster interrupted. "It can't finish. Although time effectively stops while the box enters the time loop to compute paths between your electrons, it takes a brief moment of real time to display the results. When it's ready to compute again, your electrons have moved. No two solutions can ever be the same. And don't forget, if your electrons leave the planet, you lose the bet. You agreed." Forster folded his arms. "You're trapped here."
      "Electrons aren't cities," Hutheefushee said, matter-of-factly. "Illegal data. We win."
      "No, you said, specifically, locations," Forster countered.
      "You've tricked us!" Yoongopoth cried out. "We will have to wait here forever to not lose the bet!"
      The Hammacher-Schlemmer globe suddenly burst into flames beneath the box.
      "Well, not exactly here," Forster said, waving futilely at the cloud of malodorous smoke. The buzz of the building's fire alarm rent the air like the second coming.
      "You've broken the box!" Hutheefushee cried.
      Forster considered. "No, it's just the photons from the displays." The overhead sprinkler suddenly spewed water at Forster, the aliens, Bill Gates's autobiography, Jefferson's desk, the unread student papers, and the inferno of the box; the water hissed and sizzled like bacon as it lost its battle with the box. The room fogged up with steam.
      "Exponential heat! The time loops!" Yoongopoth said, backing away.
      "The dark pit! Melt!" Hutheefushee said, backing away.
      In his feverish haze, Forster imagined the water melting them like a certain wicked witch, then realized they meant the heat output from the black hole was too rapid. "Serves you right!" he shouted. "Wait a minute, how big is the black hole? What will melt?"
      "Crisp whole planet!" Hutheefushee said. "Bad trick, very bad! Bad human!"
      Forster swallowed hard. He'd only meant to trap them logically, stall the bet for eternity or until they gave up, but being a theorist, he'd forgotten there might be physical effects to his algorithm. He could stop the box. Forster opened his mouth, remembered Meredith calling him a spineless wimp, and closed it. Forster rose and threw his head back into the sauna-like spray. He smoothed his hair as if it were a refreshing shower. "Feels like being hunted on a safari, doesn't it, Hutheefushee? God, what a paper this would make!" he shouted over the fire alarm, feeling two sorts of heat in his belly. Indeed, three: Hyped on adrenaline, he pictured himself sweeping that flirtatious Italian delivery woman off her feet if he survived.
      Thomas Jefferson's desk erupted into flames. Thick smoke began to fill the room.
      Forster knew he should leave to save his life. Instead, he advanced on the aliens, hands on hips. "Forfeit the double-or-nothing or die, you cowards!"
      The aliens heaved and grunted simultaneously. "Bah!" said Hutheefushee. "Humans!" said Yoongopoth. Fire raced across the student papers toward the aliens. Bill Gates' and Knuth's names blackened and peeled from their books. Hutheefushee waved his tentacles dismissively. "Very well, very well, you win your 'nothing.' But this doesn't prove your race is intelligent."
      "Don't bet on it!" Forster shouted, waving a fist, but the aliens and the box had blinked out, never to be seen again.