Once Upon an Algorithm Page 16
Reductions are themselves computations, and they make a handy addition to the repertoire of computational techniques, since they can be combined with other computations. For example, the problem of finding the smallest element in a list can be reduced to sorting the list and then taking the first element of the sorted list. Specifically, a reduction transforms the input (here, an unsorted list) into a specific form (here, a sorted list) on which another algorithm (here, taking the first element) can operate. Combining both computations, sorting followed by taking the first element, yields the computation that is a solution to the original problem of finding a minimum in an arbitrary list. However, it is important to take into account the runtime of reductions. For example, since the sorting step requires linearithmic time, the method obtained by this reduction does not have the same runtime as simply scanning the list for the minimum, which takes only linear time. This reduction is therefore not very useful because it leads to a less efficient algorithm.6 Therefore, the reductions between NP-complete problems must be achieved by nonexponential algorithms because otherwise a nonexponential solution to one problem would become exponential because of the reduction’s exponential runtime.
The nonexponential reduction between all NP-complete problems provides enormous leverage. Just like the wheel had to be invented by only one individual and could then be used by all humans, the solution to one NP-complete problem solves all others. And this fact leads to the question that is summarized by the famous equation:
P = NP ?
The problem was first brought up by the Austrian-American logician Kurt Gödel and was made precise in 1971 by the Canadian-American computer scientist Stephen Cook. The question is whether the class P of problems that can be solved in nonexponential (or, polynomial) time is equal to the class NP of problems that can be verified in polynomial time. Finding an exponential lower bound for NP-complete problems would provide “no” as the answer to the equation question. On the other hand, finding a nonexponential algorithm for any of the problems would yield “yes” as the answer. The tractability of a huge number of practical problems depends on the answer to the P = NP question, which emphasizes its great importance. This problem has been vexing computer scientists for over four decades and is probably the most important open problem in computer science. Most computer scientists today believe that NP-complete problems are indeed intractable and that nonexponential algorithms do not exist for the problems, but no one really knows for sure.
The Nirvana Fallacy
Prohibitive algorithmic runtime can certainly be frustrating. There is a solution for a problem, but it is too costly to be actually achieved—much like the fruits that are in front of Tantalus in the Greek myth, but are forever out of his reach. However, the discouraging facts about NP-complete problems are no reason to despair. In addition to methods to cope with the inefficiency of the algorithms, there is also a surprising upside to the limitation.
If it takes too long to find a solution to a problem, we can throw up our hands and give up, or we can try to make the best of the situation and try to find an approximate solution, one that might not be exact but good enough. For instance, if you are currently working to make a living, you are probably saving some portion of your income so that you will have enough money for your retirement. This sounds like a good plan. An arguably better plan is to win the lottery and retire right now. However, this plan rarely works out in practice and is thus not a practical alternative to the good plan you have in place.
An exponential algorithm that computes an exact solution to a problem is as impractical for large inputs as the lottery plan is for retirement. Therefore, as an alternative, one can try to find an efficient nonexponential algorithm that may not (always) compute a perfect solution but one that produces approximate results that are good enough for practical purposes—an approximation algorithm. One might consider working and saving to be an approximation to winning the lottery. It’s probably not a very good approximation, though.
Some approximation algorithms compute results that are guaranteed to be within a certain factor of the exact solution. For example, Indiana Jones can find an approximate solution to his weighing problem in linearithmic time by adding objects in order of decreasing weight. With this method, the solution is guaranteed to be at most 50% worse than the optimal solution. This doesn’t seem too promising because of the potentially low precision, but in many cases the solutions are actually much closer to the optimal solution, and they are cheap—you get what you pay for (in runtime).
In the weighing problem the simple algorithm initially has to sort the objects by weight. It then finds the first object that weighs less than the target weight and keeps adding objects until the target weight is reached. Start by adding 15, 13, and 11, which makes a total of 39. Adding the next weight, 9, would exceed the target weight, and thus we skip it and try the next one. But both 8 and 5 are also too heavy, and thus the approximate result obtained is 15, 13, and 11, which is only 3 off the optimal solution. In other words, the solution is within 7% of the optimal solution.
This strategy of repeatedly picking the largest possible value is called a greedy algorithm, since it always jumps at the first opportunity. Greedy algorithms are simple and work well for many problems, but for some problems they miss exact solutions, as in this case. It was the greedy action of taking the 11 instead of waiting for the 9 that made an optimal solution unachievable in this example. This greedy algorithm takes linearithmic runtime (caused by the initial sorting step) and is therefore quite efficient.
An important question for an approximation algorithm is how good an approximation it can produce in the worst case. For the greedy weighing algorithm one can show that it is always within 50% of the optimal solution.7
Approximations are solutions to problems that are good enough. They are not as good as an optimal solution but better than no solution at all. In Indiana Jones and the Temple of Doom, Indiana Jones and his two companions face the problem that their plane is about to crash into a mountain. The two pilots have abandoned the plane, drained the remaining fuel, and have not left any parachutes on board. Indiana Jones solves this problem by using an inflatable boat to sail the passengers to the ground, approximating the effect of a parachute. Having any approximation algorithm, no matter how crude, is often better than having no practical algorithm at all.
Make Lemonade
Approximation algorithms can ameliorate the problem of inefficiency caused by exponential algorithms. That is good news, but there is more. The fact that solutions to a particular problem cannot be computed efficiently can actually be a good thing. For example, the generate-and-test algorithm for solving the weighing problem is similar to what we have to do when trying to unlock a number lock after having forgotten its combination: We have to go through all combinations, of which there are 10 × 10 × 10 = 1,000 in the case of three single-digit dials. It is the fact that it takes a long time to try all 1,000 combinations that makes number locks somewhat effective in protecting access to bags and lockers. Of course, locks can be broken, but that is more like bypassing the problem, not solving it.
To check 1,000 combinations with an electronic computer is trivial, but for a slow human it takes long enough, which shows that efficiency is a relative notion and depends on the ability of the computer. But since algorithmic runtime is really about the growth of an algorithm’s runtime in relation to its growing input, faster computers cannot make up for the immense increase in runtime of exponential algorithms that is caused by minor increases in the size of the input. This fact is exploited in cryptography to facilitate the secure exchange of messages. Whenever you access a website whose address starts with https://, the padlock in your web browser’s address bar locks to indicate that a secure communication channel to the website has been established.
One approach to sending and receiving encrypted messages works by encoding and decoding messages with two related keys, one public key and one private key. Each participant in the
communication has one such pair of keys. The public key is known to everybody, but each participant’s private key is exclusively known by the participant. The two keys are related in such a way that a message encoded by the public key can be decoded only through the use of the corresponding private key. This makes it possible to send a secure message to someone by encoding it using that person’s public key, which is publicly known. Since only the recipient of the message knows the private key, only the recipient can decode the message. For example, if you want to check the current balance of your bank account via the internet, your web browser transmits your public key to the bank’s computer, which uses it to encrypt the amount and sends it back to your browser. Anyone who sees this message can’t decipher it, since it is encrypted. Only you can decode it in your browser using your private key.
If we didn’t have the internet and had to do this with postal mail, this would be similar to sending a box with an unlocked padlock (to which only you have the key) to your bank. The bank writes the amount on a piece of paper, puts it into the box, locks the box with the padlock, and sends the locked box back to you. When you receive the box, you can unlock the padlock with your key and see the amount. Since nobody else can unlock the box, the information is protected from unauthorized access during the transportation. In this example, the box with the open padlock corresponds to the public key, and the bank’s action of putting the sheet with the amount into the box corresponds to the encryption of the message.
An encrypted message is practically safe from unauthorized access, since in order to decode it without knowing the private key one has to compute the prime factors of a large number. While it is not known whether the computation of prime factors is an NP-complete problem, nonexponential algorithms are not known at this time, and thus it takes too long in practice to solve. Thus the difficulty of solving a problem can be utilized for protecting the transmission of information from unauthorized access.
This is not really a new idea. Moats, fences, walls, and other protective mechanisms are all based on this principle. But many of these protections can be broken. Currently, sending and receiving encrypted messages can be considered safe because of the lack of a nonexponential algorithm for prime factorization. However, as soon as anyone finds a nonexponential algorithm, that safety evaporates in an instant. If, on the other hand, someone could establish an exponential lower bound on the problem, we would be certain that encrypted messages are safe. In the meantime, our ignorance about this question keeps the method working.
Further Exploration
The adventures of Indiana Jones usually concern searches for artifacts, locations, and people. Sometimes a quest is guided by items or information gathered along the way. In these cases the path that is traveled is determined dynamically. In such stories the search leads to a list of places visited, and this list is a search path toward the final goal. Movies such as National Treasure or Dan Brown’s The Da Vinci Code follow this pattern as well.
At other times, the basis for a search is a treasure map. In this case the path is clear right from the beginning, and the search is about locating landmarks shown on the map in the real world. The book Treasure Island, by Robert Louis Stevenson, has made treasure maps famous. A treasure map is an algorithm for finding a specific location, but the algorithm can be given in quite different ways. In some stories the treasure map does not contain direct instructions for locating the treasure but rather contains clues, codes, or riddles that need to be decoded or solved. Such treasure maps do not really describe algorithms but rather problems to be solved. This is the case, for example, in the movie National Treasure, where a treasure map is hidden on the back of the Declaration of Independence that contains a code for locating spectacles that reveal further clues on the map.
The movie National Treasure also contains a riddle similar to the tile challenge faced by Indiana Jones. Ben Gates, one of the protagonists, has to infer from the keys pressed on a keyboard the password that was typed in, which requires finding the right ordering of the letters. A word or phrase whose letters denote another phrase is called an anagram. Solving anagrams is not really about sorting but about finding among all possible letter orderings a particular one. Anagrams appear, for example, in the Harry Potter stories, where “I am Lord Voldemort” is an anagram of his birth name Tom Marvolo Riddle, and in the movie Sneakers, where “Setec Astronomy,” a code name for a decrypting device, is an anagram of “too many secrets.”
In the Brothers Grimm version of the fairy tale Cinderella—in German, Aschenputtel, the bad stepmother presents Aschenputtel with the challenge to sort out lentils from the ashes, which is a simple form of bucket sort. Sometimes the events of a story also require sorting when they are narrated in nonchronological order. One extreme is the movie Memento, which presents much of its story in reverse. Something similar happens in the movie Eternal Sunshine of the Spotless Mind, where a couple undergoes a procedure to erase their memories after a breakup. The memories of one of them are then presented in reverse order. The movie Vantage Point presents the events leading up to an attempt to assassinate the U.S. President from different perspectives. Each description is itself incomplete, but adds more details and facts, and the viewer must merge all accounts together to understand the story.
David Mitchell’s book Cloud Atlas consists of several stories that are nested within one another. To obtain a completed version of the stories, one has to reorder different parts of the book. An interesting variation of the ordering challenge is presented in Julio Cortázar’s Hopscotch, which contains two different sets of explicit instructions about the order in which to read the chapters of the book.
Part II
LANGUAGES
Language and Meaning
Over the Rainbow
Doctor’s Orders
After lunch you have a doctor’s appointment. Following the exam, the physician writes a prescription and fills out a form for ordering some blood tests. You take the form to the lab, get blood drawn, and then take the prescription to the pharmacy. At this point it should come as no surprise that the lab technician, in subjecting the blood to several tests, is executing an algorithm, as is the pharmacist in preparing the prescription according to the doctor’s instructions. A noteworthy feature of this scenario is that the algorithm is defined by one person and executed by another.
This division of labor is possible only because the algorithm is written down in a language. Although the physician could also have called and instructed the pharmacist directly, this would have complicated the process, since it would have required the physician and the pharmacist to work simultaneously. The representation of the algorithm in a written form allows them to work independently of one another, and at different times. Moreover, once written, a prescription can be used multiple times.
The separation of algorithm definition and execution makes the need for a precise definition of a language evident. The physician and the pharmacist must agree on what a prescription is, what it may contain, and what it means. Your health as a patient depends on this. For example, a dosage must state its unit to avoid ambiguity. If physician and pharmacist interpret dosage in different units, ambiguity could cause the medication dosage to be ineffectively low or dangerously high. Similar agreements are required between the physician and the lab technician.
The pharmacist and lab technician are computers who have to execute the algorithms given to them by the physician. Only if they know how to read and interpret the physician’s instructions can they successfully execute them to support the physician’s goal of helping you, the patient.
The first step in executing a written algorithm is to parse it, which means to extract its underlying structure. This structure identifies the key components of an algorithm (in the case of a prescription, drug names, quantities, and frequency of intake) and how they are related (for example, whether the quantity refers to each intake or the total amount of the drug). Once the structure is identified, the meaning of the l
anguage in which the algorithm is expressed defines what exactly the pharmacist and lab technician have to do. The process of parsing is itself an algorithm for extracting the underlying structure of any given sentence.
The languages used for ordering blood work and for prescriptions are quite different. In addition to their content, they also have different external appearances. While a prescription typically consists of a sequence of words for drugs, amounts, frequency of intake, and so on, an order for blood work is routinely given by a form with several checked boxes. Often the particular format of a language is due to historical reasons, but it can also be the result of a conscious design decision to better support some of the language’s goals. For example, a form with check boxes reflects the internal structure of the language and simplifies the task of writing and interpreting (and billing) orders. It can also avoid potential ambiguities. For example, the form can be designed to prevent the selection of redundant tests, such as ordering a basic and a comprehensive test.
Language plays a central role in computer science. Without language, we could not talk about computation, algorithms, or their properties. Many domains have developed specialized languages with their own terminology and notation. In addition to using languages, computer scientists study language itself, as linguists and philosophers of language do. In particular, computer scientists address questions of how languages can be precisely defined, what features languages (should) have, and how new languages can be designed. Computer scientists study formalisms for specifying, analyzing, and translating languages, and they develop algorithms to automate these tasks.