Lady Churchill's Rosebud Wristlet No. 23
Page 2
"There it is,” the escort said.
They walked down an abandoned street among abandoned houses, toward the abandoned parking lot at the end. Dr. Luo surveyed the thing before her. She took out a pad and a pen, and made a note.
"It kind of reminds me,” said the escort, “of Tokyo. Have you ever been in the Tokyo subway? Or New York? Or Mumbai? It's kind of like that."
Dr. Luo glanced up from her pad and frowned. “There's nothing in the world,” she said, “that's kind of like this."
They walked the perimeter of the great squeaking mass, like two people strolling along a beach. The escort shivered in his shorts and button shirt. “It's creepy how it makes that noise. It kind of sighs. Kind of titters, sometimes. Kind of moans, or grunts. I knew a man who made recordings, for his thesis. He said he heard it slurping, like a really bad kiss."
"It makes all the noises,” said Dr. Luo, “that people make."
"No people that I've heard. At least, not all at once. At least, not in public. At least, not all the time."
Dr. Luo stopped walking. She made another note.
"I heard,” said the escort, nearly bumping into her, “that they tried to use lasers. Bolt cutters, crowbars, jaws of life. But nothing seems to work. The lasers are in there, now. The diodes, I mean.” He nodded with a kind of pride. “It really makes you think."
"What does it make you think?” said Dr. Luo.
The escort stood nodding with his fists on his hips. He stood without speaking for a long time. “I like the image,” he said at last. “I like the fact of it. I don't even mind the smells. It's all very intriguing to me, in its way. I just really, really, truly hate the noise."
"And yet,” said Dr. Luo, “it's all so very fragile."
"Fragile? How so? There's no way to untangle it! They've tried everything! Sharp edges, therapy, grease. They even tried hostage negotiators, once. But no one seems to get it. No one knows the trick."
"It's there,” said Dr. Luo, and pointed with her pen.
The escort looked. “There?"
"Right in there."
"Those two people?"
"Those two people holding hands."
"Right there?"
"Right in front."
"How do you know?” the escort said.
Dr. Luo turned and smiled. “That's what I do. That's my job. And as you probably should know, it's why they sent me out here. It's science. Knots. Connections. Mathematics and fractals. Order out of chaos.” She pointed again. “If they would just let go...."
"If they stopped holding hands."
Dr. Luo spread her arms.
"Amazing,” the escort said. He stepped forward and examined the couple. They were young and pretty and thoroughly connected. Whenever the woman moved, the man moaned happily. Whenever the man exhaled, the woman cooed. They looked lovely and committed, like newlyweds. But then, everyone in the mass looked that way.
The couple didn't notice the escort. They were too absorbed.
"Do you think we should tell them?” the escort said. “About their hands?"
"Why?” said Dr. Luo.
"To free them! To save them! To take this all apart. To undo this giant thing that no one else has undone."
"But it's so very interesting,” Dr. Luo said. She made another note and stood surveying the scene. The escort bent over to examine the couple. He poked with a finger at the link of their hands. Dr. Luo looked past him at the field of tangled limbs, the gross mob of connections that throbbed upon the land. She listened to the noise that was varied, content, and wet, like the aggregated burble of a billion feeding babies.
"It's a shame,” she said. “It would be so easy. To kill it, I mean. To ruin it, undo the knot.” She turned to the escort, but the escort was no longer there. She searched for his body, but without success. And yet she heard his voice in the air among others, exhaling softly a long sigh of joy.
She looked down at the couple and made a final note. Then she tapped her lip with her pen and crossed it out. She tossed her pad and pen into the pulsing mass, and walked back as she had come, along its quivering fringe.
She handed back her pass and went through the checkpoint, explaining about the fate of the escort as she walked. She stepped over the police tape and crossed the field of cones, climbed into the solitude of her black sedan. It seems right, she thought as she drove in the empty town, along the empty highway, through the emptying state. Dr. Luo was no naturalist, but she knew about laws. The thing existed: it had a right to exist. Like everything that lives and moves and feeds, it was bringing its message to the world.
[Back to Table of Contents]
The Problem of the Traveling Salesman
Ted Chiang
Suppose you're a traveling salesman and you have a list of cities you need to visit. Gasoline is extremely expensive, so the problem you're faced with is, what order should you visit the cities in to keep your fuel costs to an absolute minimum?
This is what's known in computer science as the Traveling Salesman Problem, and while it's easy to state, it's actually a very difficult problem to solve. So difficult, in fact, that a really good solution would have an dramatic impact on our understanding of the nature of the universe. In this article, I'm going to try to give a brief, non-technical explanation of why this is the case.
To begin with, let's consider the problem of sorting. When you're playing a card game, probably the first thing you do when you're dealt a hand is arrange the cards into order. A common way to do this is to take the card at the end and insert it next to another card so that the two of them are in order; then repeat with the card that's at the end now, and so on until your entire hand is in order. This is a perfectly good algorithm when you have five or seven cards to deal with; you'd probably use it even if you had ten or twenty cards.
But now suppose you're given a box containing fifty thousand index cards with words on them, and you have to sort them into alphabetical order. Now the previously described algorithm no longer seems practical. You'll probably want to try something else; for example, you might sort the cards into piles “A-M” and “N-Z,” and then sort each of those two into smaller piles, and so on. Such a technique isn't useful when dealing with just five or ten cards, but when dealing with fifty thousand, its advantage becomes apparent.
This is one of the most important criteria by which computer programmers judge an algorithm: how well does it deal with large numbers of items? We all expect that a task will take longer when you have more items to deal with; the question is, how much longer?
Let's try to get more specific. Imagine that Word Processor A takes one second to sort a list of thousand names, while Word Processor B takes two seconds. This might make A seem like the better program, but suppose we test the two programs on longer lists, two thousand or three thousand names, and their performance looks like this:
1000 2000 3000 4000
———-
A 1 sec 4 sec 9 sec 16 sec
B 2 sec 4 sec 6 sec 8 sec
B's time increases linearly with the number of items, while A's time increases with the square of the number of items. If this pattern continues, sorting ten thousand names will take A a hundred seconds, while it will take B only twenty. B is the better choice when dealing with larger numbers of items, and when it comes to computer users, you can be sure that someone will want to handle a really huge number of items.
In reality, most sorting algorithms fall somewhere in between A and B in terms of performance, but hopefully you'll have gotten the general idea: when computer programmers talk about an efficient algorithm, they're interested less in how quickly it can solve a given problem and more in whether its performance degrades when the number of items becomes huge.
Now let's return to the Traveling Salesman Problem. Just as with sorting a bunch of cards, there are a variety of different procedures for determining what is the absolute shortest way to visit all the cities. But how well do these algorithms do as the number of cities incre
ases?
It turns out, every known algorithm performs abysmally. That may sound harsh, so let's get more specific and you can judge for yourself. With the best known algorithms, the time it takes to find the solution doubles with every single city you add. That means if a program takes one second to find the shortest path connecting a hundred cities, it takes two seconds when faced with a hundred and one cities. It'll take over a minute when faced with a hundred and six cities, and over an hour when faced with a hundred and twelve cities. A hundred-and-twenty-five cities will take over a year. Think about that: the execution time has grown from one second to one year, and the number of cities has only increased by twenty-five. If you tried to give this program two hundred cities, it would take a billion trillion years.
The Traveling Salesman Problem is clearly very different from sorting when it comes to algorithmic efficiency. The issue isn't whether the Traveling Salesman Problem is soluble or not; a shortest path definitely exists. The issue is whether you can find that path in a reasonable amount of time. To computer programmers, problems of this sort are known as “intractable.” One of the reasons they're called this is that faster computers aren't of much help when tackling larger numbers of items. A computer that's twice as fast hardly makes a difference. Even a computer that's a hundred times faster won't change your situation. If you're trying to handle a really large number of items, you're essentially out of luck.
Sorting is an example of a problem in the class known as P, short for “polynomial time,” where the time to compute a solution is a polynomial function of the size of the input. (For example, if the number of items is n, the time to sort them might be proportional to n2.) By contrast, the Traveling Salesman Problem is an example of the NP-complete class of problems;[1] the time to compute a solution increases exponentially with the size of the input (proportional to 2n).
[FOOTNOTE 1: NP doesn't stand for “non-polynomial time"; it's short for “non-deterministic polynomial time.” NP is the class of problems where, if you are offered a solution, you can prove that it's correct in polynomial time. Roughly speaking, P is the class of problems for which a solution can be computed quickly, while NP is the class of problems for which a correct solution can be verified quickly.
* * * *
The category of NP-complete problems is a really interesting one. Consider some of these other examples:
* Suppose you want to pack a suitcase without going over the airline's limit of 50 lbs, but you have a whole bunch of items of varying weights. What combination of items should you put in the suitcase, so that you'll get as close to the limit as possible without going over? This is the Knapsack Problem: the more items you have to choose from, the time needed to find the absolute best combination increases exponentially.
* Suppose you have to color a map using only three colors, and you can't use the same color for two countries that border each other. This is the Map Coloring Problem: the more countries there are, the time needed to find a correct coloring increases exponentially.
* Suppose you're in high school, and you want to host a party for as many people as you can. Not everyone talks to each other; you know who will talk to whom, but for your party, everyone who attends has to be willing to talk to everyone else there. This is the Maximum Clique Problem: the more people there are to choose from, the time needed to assemble the absolute biggest invitation list increases exponentially.
These problems may appear unrelated, but in the 1970s, mathematicians proved that it was possible to convert any one these problems to the Traveling Salesman Problem, or into each other. This means that if you can find a way to solve any one of these problems efficiently, you know how to solve all of them efficiently. All of these problems are, at some level, the same problem.
Over three thousand NP-complete problems have been identified so far, and they've been found in virtually every area of scientific inquiry, from economics to biology. Even common games like Minesweeper and Sudoku has been shown to be NP-complete. (Imagine how long it would take to solve a Sudoku puzzle involving the numbers one to ten thousand.) More serious examples involve building digital circuits, solving various classes of equations, and generating mathematical proofs. All of these problems are exactly as hard as each other, and a really good solution to the Traveling Salesman Problem would be a good solution to all of them.
The question of whether an efficient way to solve these problems exists is known as the P=NP question, and it's probably the greatest unsolved problems of computer science. Most experts believe that P does not equal NP, but no one has been able to prove it (although some have proven that ordinary techniques for mathematical proof are incapable of answering the question). An organization called the Clay Mathematics Institute offers prizes of a million dollars each for solutions to seven unanswered questions in mathematics, and the P=NP question is one of them.
(Despite the importance of the P=NP question, I haven't seen it mentioned much in science fiction. Charles Stross mentions it briefly in his short story “Antibodies,” in which an efficient algorithm for the Traveling Salesman Problem ushers in the Singularity, but I'm not aware of any other examples. Probably its best known appearance in popular culture is a Halloween episode of The Simpsons: when Homer becomes three-dimensional and explores a wonderland of computer-generated imagery, the equation “P=NP” is visible in the background. There's also an episode of Futurama where Fry and Amy are making out in a closet at Planet Express, and two books on a shelf behind them are labeled P and NP.)
If it turned out that P were equal to NP, the consequences would be hard to overstate, because it would mean that computer programs could efficiently discover mathematical truths. For example, the other six problems listed by the Clay Mathematics Institute, some of which are over a century old, could all be solved quickly. Some people have said that if P=NP, then creativity could be automated. There's a sense in which mathematicians’ jobs is to look for the needles of correct answers within vast haystacks of incorrect ones (indeed, the same could be said of many people's jobs); an efficient algorithm for the Traveling Salesman Problem would, in effect, let us find those correct answers mechanically.
Is it possible that a fundamental advance in computer technology will make NP-complete problems easily solvable? Some scientists have investigated whether physical phenomena might be able to perform the equivalent of NP-complete computations quickly. Soap bubbles, for example, assume a shape that minimizes their surface area; a few individuals have tried to use this natural behavior to solve a specific NP-complete problem called the Steiner Tree Problem. They built an apparatus of two plexiglass sheets connected by pegs, dipped the whole thing into soapy water, pulled it out, and watched to see if the soap film took the shape of the best way to connect the pegs. If it had, then nature would have done something that digital computers can't do, but it turns out that soap film cannot reliably find the best solution.
What about quantum computers, which operate on fundamentally different principles than conventional computers? They're often touted as being unbelievably powerful, and may render current forms of encryption obsolete. To date, however, it appears that quantum computers are likewise unable to solve NP-complete problems efficiently; if at some point it's proven that they can, that would actually constitute an important discovery about the nature of quantum mechanics.
Other hypothetical types of computers that have been offered as ways to solve NP-complete problems efficiently have, under examination, been shown to violate our understanding of physics. Coincidentally, physicists have investigated what kinds of problems a computer could and could not solve if it were able to send signals back in time, and it turns out that such a computer could solve NP-complete problems quickly; in other words, an efficient solution to NP-complete problems might be as remote a possibility as time travel. It's almost as if the laws of the universe were designed to keep certain problems hard to solve.
In one respect, it may seem frustrating that, no matter how advanced ou
r technology becomes, some problems will forever be resistant to easy solutions. But this could also be interpreted as good news, because it means that creativity can't be automated. The intractability of the Traveling Salesman Problem means that there will always be a need for ingenuity and insight. That's a relief, isn't it?
[Back to Table of Contents]
Heliotrope Hedgerow
Christa A. Bergerson shall we now enter the thorny thicket the floor of the woods so fully clothed wicked roses strangling pale picket how neatly the grass seems to be mowed behind the heliotrope hedgerow lives
Hecate, a lady who surely knows the vision of Hermes Trismegistus and emerald tablets that ghost grass grows follow her to the other side of time visit the man with the thousand faces better hurry to be the first in line pray that you will be in his good graces take the key and cross through the clover door transcend sublunary forevermore
[Back to Table of Contents]
The Emily(s) Debate the Impact of Reclusivity on Life, Art, Family, Community, and Pets
Kat Meads
The excitement—electrifying! The tension—tremendous! For here, tonight, together, in the flesh, as never before and never again, Miss Emily Elizabeth Dickinson, maid of Amherst, and Miss Emily Jane Brontë, maid of Haworth, will appear, discuss their life and work and respond to questions, as time permits. Representatives from each party have agreed to these conditions and have sworn, under threat of legal reprimand, that their clients will indeed show up and show themselves on a stage occupied just now by two empty chairs, a table, two glasses and tumbler of water. (Also provided: two mini-microphones, should either author wish to improve her vocal projection.)
And we in the audience? Near mad with anticipation, awed and exhilarated by the very prospect of sharing the same ether as such legendary, reticent beings. The potential staggers and stuns. The possibility of so many intimate facts divulged! The likelihood of so many wry and spicy details revealed! The depth and breadth of titillating disclosure is scarcely to be imagined. From front row to back: nervous coughs and fidgets, the rustle of notebook pages, for everyone attending this momentous event will take, must take, notes.