Jon Kleinberg, Cornell University, and Christos Papadimitriou, University of California, Berkeley

One of the great obsessions of Renaissance sages was the solution of polynomial equations: find an x that causes a certain polynomial to evaluate to 0. Today we all learn in school how to solve quadratic equations (polynomial equations of degree two, such as ax² + bx + c = 0), even though many of us have to look up the formula every time (it’s ). Versions of this formula were known to the Babylonians as early as 2000 BC, and they were rediscovered in many ancient cultures. The discovery of similar but much more complicated formulas for solving equations of degree three and four—the cubic and quartic formulae—had to wait until the 16th century AD. During the next three centuries, the greatest minds in Europe strove unsuccessfully to discover the quintic formula, cracking equations of degree five, until the flowering of modern algebra brought the quest to a sudden, surprising resolution: a proof that there is no quintic formula.

This story, on first hearing, can engender a few natural reactions. Among them, surprise—what’s the obstacle to a quintic formula? Why was it so hard to prove it didn’t exist? And, more subtly, a mild sense of perplexity—what do we mean by a quintic formula anyway? Why can’t we write “the largest x such that ax⁵ + bx⁴ + cx³ + dx² + ex + f = 0” and declare this to be a formula?

So we back up. By a “formula” in this story, we meant a particular thing: a finite sequence of steps that begins with the given values of the coefficients and ends with a root x; each step consists of one of the basic arithmetic operations applied to certain of the quantities already computed, or else it consists of the extraction of a root of one of the quantities already computed. Now we can assert more precisely, thanks to the work of the 19th-century mathematicians Abel and Galois: there is no quintic formula.

Viewed from the safe distance of a few centuries, the story is clearly one about computation, and it contains many of the key ingredients that arise in later efforts to model computation: We take a computational process that we understand intuitively (solving an equation, in this case), formulate a precise model, and from the model derive some highly unexpected consequences about the computational power of the process. It is precisely this approach that we wish to apply to computation in general. But moving from this example to a fully general model of computation

Front Matter (R1-R14)

Prelude: Emily Shops at VirtualEmporia.com (1-8)

Part One: The Essential Character of Computer Science1 The Essential Character of Computer Science (9-24)

Part Two: Selected Perspectives on Computer Science 2 Exponential Growth, Computability, and Complexity (25-56)

3 Simulation (57-64)

4 Abstraction, Representation, and Notations (65-78)

5 Data, Representation, and Information (79-100)

6 Achieving Intelligence (101-126)

7 Building Computing Systems of Practical Scale (127-158)

8 Research Behind Everyday Computation (159-178)

9 Personal Statements of Passion About Computer Science Research (179-192)

Appendix: Agenda of July 25-26, 2001, Symposium (193-194)

Plates (195-202)