“I like cinnamon, so I’ll season the soup with that. Well, the flavor of basil is nice too, so in that goes. And pesto! And chocolate chips! And chicken fingers! And motor oil!”

Cooking disasters

Those just learning how to cook often become overeager and combine too many conflicting ingredients. The inevitable result is an abomination of nature necessitating a thoroughly trained team of serious men in haz-mat suits who say grizzled things like “Holy mother of God,” in dramatic drawn-out timbre. The problem us novice cooks face is that how good something tastes is not a simple combination of how good the individual ingredients taste.

Cooking is surprisingly deep.  Nearly always, an outsider’s view of a particular subject is off-base. For example, people not familiar with the wild world of computer science generally assume that it is all about fixing computers, when in fact it all about hard drugs and loose women — fine, ok, not that either. Surprisingly, computer scientists are not always experts at figuring out why ITunes won’t load or deciphering arcane error codes in Microsoft Excel. Instead, computer scientists are universally adept at translating human thought and language into an algorithm that a computer can “understand” and run. Us computer scientists take a process (for example, sorting a list of numbers) and turn it into a recipe so unambiguous and literal that a dumb-as-rocks CPU can follow the instructions. Outsiders don’t generally know this, though. Silly geese.

I was mistaken about cooking in a similar way. My outsider’s view of cooking was that it was fundamentally about following directions. You take a recipe, and the more accurately you follow that recipe, the better you are at cooking. But this is a superficial view of cooking; to a certain point your technical ability to follow recipes is important. However, the undeniable rock star with only a tenuous grasp of English, traditional musical knowledge, and basic instrumental skills illustrates that technique is not everything. And for all those cooks that do master the technical skills, what then distinguishes a brilliant chef?

A deeper view might focus not only on technical skill, but also on the talents required to bring delicious new recipes into reality. The challenge in making good recipes is that on some level you need to understand how different ingredients and cooking methods will interact to produce a taste. That is, to tweak an existing recipe so that it tastes better, you might identify some deficiency in the flavor and then figure out how to remedy that problem.

This is sometimes easy — if the food is too sour, adding a sweetener like sugar will generally help. However, improving a complex mix of spices requires understanding how those spices interact together, what is missing from the interaction, and how adding or removing a quantity of another spice can remedy the flaw. In other words, becoming a master chef requires building a detailed mental model that maps recipes to how they will taste.

You must become a human oven simulator.

Besides the tasty products it leads to, cooking can also provide an intuitive metaphor that can illustrate complex issues in computer science or mathematics. For example, say you have a spicerack and want to make a mix of spices (say, to season a soup) that tastes better than some existing mix (suck it, Lowry’s seasoning salt). Surprisingly,this is actually a very hard problem because spices interact in complicated ways. The effect of a spice on your tastebud — whether it will improve the flavor or not –depends on the context of that spice, i.e. what spices it is mixed with. For example, chilli powder may taste good when mixed with paprika and black pepper, but less so with vanilla extract. So, making a better spice mix problem is surprisingly hard. So hard that it is an NP-complete optaimization problem in disguise.

NP completeness: Scary-sounding yet simple

Don’t be afraid. Here comes the segue into theoretical computer science. I promise that I’ll keep things understandable. First, take the triple integral of the hyperbolic tangent of x, and then obviously we will apply the Weissman transformation, because only a complete idiot wouldn’t! Just kidding.

Although at first you might reasonably think that it has absolutely no relation to real life, theoretical computer science deals with an abstraction of real-life processes called algorithms. This is similar to how the ‘x’ in ‘x+3=5′ in algebra is an abstraction of a number. So just as ‘x’ could represent any real-life quantity — in this equation it could readily represent the number of warm tequila shots needed to induce vomiting — an algorithm in computer science can represent any real-life process, like the steps in a recipe one follows when cooking.

Now, before this digression I had mentioned that trying to improve a mix of complex spices is equivalent to an NP-complete optimization problem in theoretical computer science. ‘Optimization’ is just a fancy word for ‘trying to improve’, but what is ‘NP-complete’?

NP-complete means that a problem is very difficult to solve, and yet a correct answer is easy to verify (for example, it is difficult to get a girl’s number at a club when you are dressed up like a giant banana, but you’d know you were successful by dialing the number on a piece of napkin and hearing her voice). For our spice example, simply by tasting both the better spice mix and the benchmark Lowry’s seasoning salt (sponsor me?), you can easily verify if the problem has been solved or not: Does the new mix taste better? However, to come up with this better spice mix may take a lot of work.

In fact, one of the biggest open problems in theoretical computer science is whether you can find some way to easily solve  NP-complete problems, or whether they can only be solved by doing an outrageous amount of brute-force work (e.g., trying every conceivable combination of spices). This is known as ‘P=NP?’. P is the set of easily-solved problems, and NP is the set of easily-verified problems. Most people think these two sets are not the same, that some easily-verified problems (for example, our spice rack optimization problem) cannot be easily solved. But as of yet no one has been able to prove it, though many geniuses have tried.

Reverse-engineering Coke’s secret formula or a rocking chair

There’s an interesting analogy between the idea of recipes in cooking and that of a computer program in computer science. Both recipes and programs describe processes, but a recipe is interpreted by a human and a computer program by a computer. With this rough analogy in mind, I’ll ask a seemingly unrelated question: Is it possible to reverse-engineer any recipe? That is, by looking at the cooked food, can we uncover a potential list of ingredients and how they are to be combined and cooked, that generates something that tastes the same? Perhaps a good enough chef, given enough time and smarts could deduce the recipe for any food.

But maybe this underestimates the trickiness of the problem. While chefs are well-acquainted with foods that taste good or that are made in typical ways, what about recipes that are random combinations of different ingredients and cooking methods (grilled cheerio-tuna paste with creamed-celery and vinegar marinade)? They might generate gross, weird foods that a chef would have no experience in dealing with. These strange creations would lie outside the chef’s mental model of food-tastes and might be more difficult to reverse-engineer into a recipe.

The difficulty of reverse-engineering a complex artifact (like a cooked food) is not specific to cooking. For example, take the art of wood-working. When doing wood-working, one applies tools (saws, drills, chisels) in a systematic way to achieve a certain appearance in the wood. That is, there are certain techniques that are performed on the wood in a certain order, like steps in a recipe, to transform the wood in a particular way. So, given a final assembled piece of worked wood, is it always possible to determine a reasonably short list of  actions similar to those that were actually taken? With simple pieces, it is probably easy to determine how to achieve a particular look. However, with a large set of complex cuts and chisels, trying to deduce the “recipe” to create that finished piece may be very difficult.

Woodworking with 1′s and 0′s

While these strange reverse-engineering situations might seem pointless, they relate to the grand issue of “P=NP?” in computer science (can difficult problems that have easily verified solutions be solved easily?). Computer programs can be seen as abstract versions of recipes or wood-working plans. But instead of  a cooked food or a finished piece of wood, a computer program crafts abstract data, a series of bits, 1′s and 0′s. Computer programs consist of instructions, much like recipes, that run for awhile and do various calculations on data.  For example: “Take the number 27, multiply it by 3, keep dividing it by two until the remainder is 0, then print out how many times we divided.” We can consider a type of program that prints out a single number on the display when they finish. We can view this lonely number as the product, what the algorithm creates, and abstract equivalent of food in recipes, or the final piece when woodworking.

So, we can ask a reverse-engineering question about computer programs similar to the ones we asked earlier about cooked food or finished pieces of wood. Can we examine any given very long number (say tens of thousands of digits) and then determine a small program, if one exists, that produces it? It is important that the program be small, because a simple way of generating any number is just to say “Print x” where x is that big number. This isn’t very interesting, it would be similar to if the recipe for a particular cake was an atom-by-atom description of the cake, or if the instructions for creating a table for woodworking detailed how to glue together a huge amount of tiny wood pieces.

For example, if the binary number (series of 1s and 0s) was “111111111111111111111111111″ a simple, quick algorithm for making this string is just “Print 1 thirty times.” This is a good recipe for making that string of bits. For a random string of bits, like “101101001011110010101111″ there may be no short recipe for constructing it. Can you think of one?

We also might want to say that a number-recipe program shouldn’t run forever. That is, some programs might specify really long calculations that could take eternity for a real computer to run. Like: “Consider all of the numbers less than 20 trillion, factor them, and add all of their factors together.” A time restriction makes sense because we also wouldn’t want a recipe for cheesecake that requires 33.5 degree heat applied for a millennium. So perhaps we add some arbitrary cutoff, say, that a number-recipe program can only run for a number of steps that is proportional to the size of the target number, the one to be printed out. If the cooked number is 1000 digits long, perhaps the program can only run for 1000 squared, or 1,000,000 steps. With these constraints considered, what we are asking then is if given a really long number, we can come up with a relatively short, fast recipe for generating that number.

For example, imagine our problem is to find a small, fast recipe for the number “10110111011110111110 …” (what is the pattern here?) that continued until there were a thousand ones followed by a last zero. A potential recipe is “Do the following one thousand times: Print ’1′ however many times we’ve done this step and then print a single ’0′.”

Look at me, now back at NP…I’m on a horse

Now to tie this sprawling post together: How does this number-recipe-writing problem relate to “P=NP?” Remember that this grand unsolved problem in computer science asks if every problem in which solutions are easily verified (NP) is also easily solved (P). Our reverse-engineering problem is easily verified (it is in NP): If you take a short program and run it, you can discover if it stops running within the time limit and if the number it outputs at the end is the one we are interested in. What is not clear is if it is also in P, that is, whether NP problems are easily solvable.

Intuitively, it seems like this problem shouldn’t be easily solvable, that it should not be in P. The space of possible programs is so vast, and the mapping between programs and output numbers so strange, that there should be no automatic way of reverse-engineering a given number to deduce its origins . This is why I, and most computer scientists, believe that P is not equal to NP, though it is still an unsolved problem.

So, as we reach the end of this long strange thread, the take home message is that although it seems far removed from reality, theoretical computer science actually does have something to say about what is easily possible in reality. That is, it may be impossible to easily reverse-engineer an arbitrary process, whether it is a computer program, a recipe, or instructions to craft wood. Another take-home message is that to avoid creating kitchen monstrosities, when first learning to cook it is good to stick to the recipes instead of boldly going where no man has, nor ever should go, into that wild and pungent frontier of culinary catastrophes.