Departments

By Moshe Y. Vardi

Communications of the ACM,

March 2019,

Vol. 62 No. 3, Page 7

10.1145/3306448

Comments (1)

When I was 10 years old, my math teacher started a Math Club. It was not popular enough to last more than a few weeks, but that was long enough for me to learn about matrices and determinants. When I came home, my mother asked me how the club had been. “Beautiful,” I answered. “Do you mean, ‘interesting’?” she inquired. “No,” I said, “Beautiful!” While some people find mathematics befuddling, others find it elegant and beautiful. The mathematician Paul Erds often referred to “The Book” in which God keeps the most beautiful proofs of each mathematical theorem. The philosopher Bertrand Russell said, “Mathematics, rightly viewed, possesses not only truth, but supreme beauty.” The beauty can be compelling; something so beautiful must be true!

But the seductive power of mathematical beauty has come under criticism lately. In *Lost in Math*, a book published earlier this year, the theoretical physicist Sabine Hossenfelder asserts that mathematical elegance led physics astray. Specifically, she argues that several branches of physics, including string theory and quantum gravity, have come to view mathematical beauty as a truth criterion, in the absence of experimental data to confirm or refute these theories. The theoretical physics community, she argues, is falling victim to group thinking and cognitive bias, seduced by mathematical beauty. About 10 years ago, in the wake of the 2008 financial crisis, the Nobel Laureate economist Paul Krugman made the same point with respect to economics and mathematics in an influential article titled “How Did Economists Get It So Wrong?” His main answer was: mistaking mathematical beauty for truth. “As I see it,” wrote Krugman, “the economics profession went astray because economists, as a group, mistook beauty, clad in impressive-looking mathematics, for truth.”

So both physics and economics have, arguably, been lost in math. What about computer science? Specifically, what about theoretical computer science (TCS)? TCS is surely blessed with mathematical beauty. As a graduate student a long time ago, it was mathematical beauty that attracted me to TCS, and continued to lead my research for many years. I find computational complexity theory (or complexity theory, for short), with its theorems (for example, the time-hierarchy and space-hierarchy theorems) and its open questions (for example, *P* vs *NP*), to be hauntingly beautiful. Beauty, yes; but what about truth?

Physical theories describe the physical world, and by their “truth” we refer to the fidelity in which they describe this world. Economic theories describe economic systems, but by their “truth” we refer not only to the fidelity in which they describe such systems but also to the quality of the guidance they offer to business people and policymakers. I believe complexity theory is similar to economic theories in that respect. It should not only provide a theoretical framework in which we can study the performance of algorithms, but it should also offer sound guidance to algorithm designers and system developers who use algorithms. So how good a theory is complexity theory from that perspective?

It is clear what it means to measure the performance of a specific algorithm *A* on a specific problem instance *I.* But complexity theory aims at describing the performance of *A* over the space of *all* problem instances and it does so by abstracting away from individual problem instances. The typical way in which we do this abstraction is by considering *all* problem instances of length *n*, and asking for upper and lower bounds on algorithmic performance (usually in terms of time and memory utilization) as a function of *n.* This approach is referred to as the *worst-case* approach, as it focused on the most challenging problem instance of each length *n.* If the upper bound that we can prove is one of a slow-growing function, for example, *cn log n*, for a small constant *c*, then we have a guarantee of good performance on *all* problem instances. But, in general, most upper and lower bound are much less useful. For example, an exponential lower bound just says some problem instances are hard, but says nothing about the practical significance of such instances.

In previous columns I have discussed this gap between theory and practice in specific settings. As I pointed out, program termination may be unsolvable in theory but solvable in practice,^{a} while Boolean satisfiability may be intractable in theory but tractable in practice.^{b} In both cases, the worst-case approach is simply too pessimistic and tells us too little about algorithmic performance in practice. Beauty does not necessarily entail truth. Going beyond worst-case complexity is a key challenge in complexity theory and is the subject of much current research. (See Tim Roughgarden’s Review Article on p. 88).

Follow me on Facebook, Google+, and Twitter.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2019 ACM, Inc.

## Comments

##### Timothy Davis

February 25, 2019 09:09

Is code beautiful in a different way that math is beautiful?

The mathematical statement $x=A^{-1}b$ is beautiful, except that it’s a terrible way to solve a linear system. In most cases it’s inaccurate in the dense case, and O(n^3) time in the sparse case, whereas a good sparse solver can take O(n) time on the same matrix. So I would say that while x=inv(A)*b in MATLAB looks beautiful, underneath it is truly ugly. It’s the MATLAB expression x=Ab that’s truly beautiful.

I call this ‘MATLAB inv abuse’, and it’s surprisingly common, in spite of the fact that the MATLAB code analyzer warns against it. From my count, 6% of all user contributions at MATLAB Central use inv(A), and almost all of them are ‘inv abuse’, I would hazard a guess that the writers of these codes are being misled by the beauty of the mathematical statement $x=A^{-1}b$, to write the ugly ‘x=inv(A)*b’.

And yet beauty in code is important. I would say that when the code is well-written and well-documented, when the logic is sharp and clear, when the code is free of bugs, when the algorithm embodied by the software is both elegant and *fast* (in theory or in practice on actual problems, or ideally both), then a computer scientist would say it’s truly beautiful.

Would this be a good working definition of beautiful code? That’s an open question; I may be missing something important.

Math is beautiful if it’s elegant and expressive (say in a proof). It doesn’t matter if the proof of a conjecture A calls on a powerful theorem B that has a long and hard-to-read proof. In fact, that could make the proof of A still more beautiful, in its simplicity.

But that doesn’t work for code. x=inv(A)*b calls on the powerful sledgehammer inv(…), which is really horrible when A is sparse.

Is code beautiful when it not only looks beautiful (easy to write, read, and play with like Legos), but also when it *acts* beautiful?

Displaying **1** comment