Ada’s Algorithm.

My top 50 free agent rankings went up Friday for Insiders, following by the “deleted scenes” post with capsules on four guys whom I wrote about before their employers picked up their club options. I’ve also got buyers’ guides to catchers and to corner infielders up, with middle infielders due on Tuesday.

Everything seems to be coming up Ada Lovelace lately; largely overlooked in her own time because she was a woman in the early Victorian era and was better known as the one legitimate offspring of the rake Lord Byron, she’s now widely recognized as the creator of the first machine algorithm, the primary ancestor of the modern computer program. The Department of Defense named a programming language (Ada) after her in the early 1980s, and she’s appeared in numerous works of fiction (such as William Gibson’s The Difference Engine) and non-fiction (including a brand-new short work aimed at schoolchildren called Ada Byron Lovelace and the Thinking Machine) over the last 25 years. Since my daughter was working on a short presentation on Lovelace – all the kids were asked to pick a scientist, and she was pissed off because there was only one woman (Marie Curie, of course) on the original list of assignments – I picked up James Essinger’s 2014 biography, Ada’s Algorithm: How Lord Byron’s Daughter Ada Lovelace Launched the Digital Age, which had most of the key details but is padded with a lot of less critical material.

Ada Lovelace’s place in history comes from her friendship with Charles Babbage, who designed (but never built) the first computers, one called the Difference Engine, of which he built one-seventh, and another called the Analytical Engine, which he never built at all due to the prohibitive cost and lack of manufacturing facilities capable of building all of the cogswheels the device required. Babbage was a bit of a mad scientist, prone to emotional outbursts and self-destructive arguments that cost him any shot to gain the funds necessary to build even part of either Engine beyond what he built. He also lacked Ada’s communications skills, and when the Italian mathematican (and later Prime Minister of Italy) Luigi Federico Menabrea wrote a paper describing Babbage’s Analytical Engine, Lovelace translated it into English and supplemented it with her own Notes, the latter of which ran more than twice as long as Menabrea’s original article, and included the algorithm that earned her posthumous fame. She saw the potential of Babbage’s machine that even Babbage did not – that programmers could use it to solve all kinds of mathematical problems beyond mere arithmetic, as long as the programmer could conceive the necessary series of steps for the calculations.

Lovelace died of uterine cancer at 36, and much of the detail of her life is lost both to time and, it’s believed, to her mother’s decision to destroy much of Ada’s correspondence after the latter’s death. Even many of the letters she exchanged with Babbage are gone, leaving any biographer with relatively meager material from which to construct a story of her life. Essinger barely makes it past 200 pages, and even to get to that point he has to fill with material that’s not all that relevant to the reader primarily interested in Ada’s Notes and the algorithm of the book’s title. For example, we don’t need two chapters on Lord Byron, and I was certainly glad I got the book away from my daughter (who found it boring anyway) before she got to the mentions of his incestuous relationship with his half-sister Augusta or the story of how his nanny would take him into her bed, masturbate him, and then later turn around and beat him, often doing both things in the presence of her friends. (That material would seem essential in any biography of Byron himself, though, since it probably explains his later promiscuity and other “immoral” behavior relative to the mores of the era.) Byron was out of Ada’s life for good while she was still an infant, and including such details on his life seems more than just out of place but almost pandering.

Essinger gives us too much of the text of some of her less relevant letters, and inserts his own speculation on things like whether she might have met certain personages of the era, like Charles Darwin, or whether Babbage was in love with Ada, for which there’s no tangible evidence. The first hardcover edition also has numerous typos and minor errors in the text – for example, using “inconceivable” when he meant “conceivable,” which is kind of a weak word anyway – that further added to my impression that I was reading Essinger’s thoughts and opinions rather than a narrative rendering of her life. It seems that we don’t know enough about Ada Lovelace for a full biography, but that doesn’t quite justify surrounding what we do know with speculation or tangential details.

Next up: Speaking of Gibson, I’m reading Mona Lisa Overdrive, the third book in his Sprawl trilogy, which began with the Hugo-winning Neuromancer.

The Golden Ticket.

Lance Fortnow wrote a piece for Communications of the Association for Computing Machinery in 2009 on the state of the P vs NP problem, one of the most important unsolved problems in both mathematics and computer science. That article led to the short (~175 page) book The Golden Ticket: P, NP, and the Search for the Impossible, which I recently read in its Kindle edition (it’s also on iBooks); Fortnow does a solid job of making an abstruse problem accessible to a wider audience, even engaging in some flights of fancy describing a world in which P equals NP … which is almost certainly not true (but we haven’t proven that yet either!).

P vs NP, which was first posed by Kurt Gödel in 1956, is one of the seven Millennium Problems posed by the Clay Mathematics Institute in 2000; solve one and you get a million bucks. One of them, proving the Poincaré Conjecture (which relates to the shape of the universe), was solved in 2010. But if you solve P vs NP affirmatively, you can probably solve the remaining five and collect a cool $6 million for your problems. You’ll find a box of materials under your desk.

Of course, this is far from an easy question to solve. P and NP are two classes of problems in computer science, and while it seems probable that they are not equivalent, no one’s been able to prove that yet. P is the set of all problems that can be quickly (in deterministic polynomial time – so, like, before the heat death of the universe) solved by an efficient algorithm; NP is the set of all problems whose solutions, once found, can be quickly verified by an efficient algorithm. For example, factoring a huge composite number is in NP: There is no known efficient algorithm to factor a large number, but once we’ve found two factors, a computer can quickly verify that the solution is correct. The “traveling salesman problem” is also in NP; it’s considered NP-complete, meaning that it is in NP and in NP-hard, the set of all problems which are at least as hard as the hardest problems in NP. We can find good solutions to many NP-hard problems using heuristics, but we do not have efficient algorithms to find the optimal solution to such a problem.

If P does in fact equal NP, then we can find efficient algorithms for all problems in NP, even those problems that are NP-complete, and Fortnow details all of these consequences, both positive and negative. One major negative consequence, and one in which Fortnow spends a significant amount of time, would be the effective death of most current systems of cryptography, including public-key cryptography and one-way hashing functions. (In fact, the existence of one-way functions as a mathematical truth is still an unsolved problem; if they exist, then P does not equal NP.) But the positive consequences are rather enormous; Fortnow gives numerous examples, the most striking one is the potential for quickly developing individualized medicines to treat cancer and other diseases where protein structure prediction is an obstacle in quickly crafting effective treatments. He also works in a baseball story, where the game has been dramatically changed across the board by the discovery that P=NP – from better scheduling to accurate ball/strike calls (but only in the minors) to the 2022 prohibition of the use of computers in the dugout. It’s Shangri-La territory, but serves to underscore the value of an affirmative proof: If we can solve NP problems in deterministic polynomial time (as opposed to nondeterministic polynomial time, where NP gets its name), our ability to tease relationships out of huge databases and find solutions to seemingly intractable logical and mathematical problems is far greater than we realized.

Of course, P probably doesn’t equal NP, because that would just be too easy. That doesn’t mean that NP-complete problems are lost causes, but that those who work in those areas – operations research, medicine, cryptography, and so on – have to use other methods to find solutions that are merely good rather than optimal. Those methods include using heuristics that simplify the problem, approximating solutions, and solving a different but related problem that’s in P. If Fortnow falls short at all in this book, it’s in devoting so much more time to the brigadoon where P=NP and less to the likely real world quandary of solving NP-complete problems in a universe where P≠NP. He also gives over a chapter to the still theoretical promise of quantum computing, including its applications to cryptography (significant) and teleportation (come on), but it seems like a digression from the core question in The Golden Ticket. We don’t know if P equals NP, but as Fortnow reiterates in the conclusion, even thinking about the question and possible approaches to proving it in either direction affect work in various fields that underpin most of our current technological infrastructure. If you’ve ever bought anything online, or even logged into web-based email, you’ve used a bit of technology that only works because, as of right now, we can’t prove that P=NP. For a very fundamental question, the P vs NP problem is scarcely known, and Fortnow does a strong job of presenting it in a way that many more readers can understand it.

If this sounds like it’s up your alley or you’ve already read it, I also suggest John Derbyshire’s Prime Obsession, about the Riemann Hypothesis, another of the Clay Millennium Institute’s six as-yet unsolved problems.