Mail to a friend · Print this article · Previous Columns Tony Phillips' Take on Math in the Media A monthly survey of math news

# This month's topics:

## Complexity theory in the New York Times

"Arts Beat" on March 15, 2012: Jennifer Schuessler uses the Broadway production of "Death of a Salesman" opening that day as an excuse to riff on one of the Clay Mathematics Institute's millenium problems. "Willy Loman ... may think he has problems. But it turns out he's got nothing on the hypothetical road warriors ... who are pushed to visit hundreds, thousands, even millions of cities, mostly in pursuit of someone else's mathematical glory." Basing herself on the recent book "In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation" by William J. Cook (Georgia Tech), she sketches the history of the Traveling Salesman problem: it dates back to the early 19th century; it "was born as a major mathematical preoccupation in the late 1940s, around the same time as Loman himself, but has gone on to have a far more satisfying career;" the name was in fact coined by Julia Robinson in 1949. The problem is stated ("involves finding the most efficient route among geographical points") and we get an idea of its complexity: "Mapping out an optimized route for a 33-city version of the problem used in a 1962 contest sponsored by Procter & Gamble, Dr. Cook notes, involves measuring [$1.3\times 10^{35}$] possible routes, which would take the Energy Department's Roadrunner supercomputer roughly 28 trillion years."

A Traveling Salesman problem with 33 cities from a 1962 Procter & Gamble contest (more details on this larger image).

"Procter & Gamble's 33-city contest went unsolved in 1962." Here is Prof. Cook's more recent solution. Images courtesy of William Cook.

Schuessler is a bit vague on the exact nature of the Clay Institute's challenge but she reports Cook's prediction: "The salesman may defeat us in the end ... but not without a good fight."

Computational complexity turns up again in the Times, on March 20, this time in a story about detecting cheating in chess. Dylan Loeb McClain tells us about Kenneth W. Regan, "an associate professor of computer science at the University of Buffalo who is also an international master at chess." Regan has worked on "constructing a mathematical proof to see if someone has cheated," based on "a model of how often the moves of players of varying ability match those of chess programs" constructed from the records of some 200,000 games from the last two centuries. But high-tech fraud detection is only a sideline for Prof. Regan: "his principal focus is the holy-grail math problem P versus NP. (P versus NP is about whether problems that have solutions that can be verified by a computer can also be solved quickly by a computer.)"

## Spermatozoon calculus

In an article in the February 27, 2012 Journal of Cell Biology a team led by Luis Alvarez (CAESAR, Bonn) describes how sperm (they studied those of the sea urchin Arbacia punctulata) use the gradient in $[\mbox{Ca}^{2+}]_i$, the intracellular calcium ion concenration, to direct their swimming. Their main result is that the time derivative of $[\mbox{Ca}^{2+}]_i$ controls the path curvature.

The path traced by an Arbacia spermatozoon, colored by the time derivative of the intracellular calcium ion concentration. The magnitude of the derivative correlates strongly with the curvature of the path. Image © Alvarez et al., from "The rate of change of $\mbox{Ca}^{2+}$ concentration controls sperm chemotaxis," JCB 196 653-663, published by Rockefeller University Press.

As the authors explain, the flagellum, the single oar with which the spermatozoon sculls about, "serves both as a propeller and antenna that detects chemical cues." They describe a "chemical differentiator model" which would couple changes in $[\mbox{Ca}^{2+}]_i$ to "flagellar assymetry," producing more sculling on one side than on the other and hence curvature in the path. This work was picked up by Pierre Barthélémy in Le Monde online's "Passeur de Sciences" blog, under the heading "Les spermatozoïdes savent calculer," March 22, 2012.

## Pi Day in Greenburgh

According to the Daily Greenburgh (Westchester County, New York; March 13, 2012) Greenburgh Central 7 School District Superintendent Ronald Ross "has declared Wednesday, March 14 a day off for all district students in honor of 'Pi Day.' Pi, the ratio of the circumference of a circle to its diameter, is approximately 3.14, thus 'Pi Day.'" During their day off, students are to contemplate mathematics. This is especially encouraged for those taking part in an enrichment program scheduled this spring and run by the mathematician Jonathan Farley, who is quoted: "It's open to any kid who has a love of math and wants to explore something different." Article contributed by Rick Pezzullo.

Tony Phillips
Stony Brook University
tony at math.sunysb.edu