→ September 2, 2017
→ By

Stick to baseball, 9/2/17.

For Insiders this week, I wrote four pieces. I broke down the Astros’ trade for Justin Verlander and the Angels’ trade for Justin Upton. I put up scouting notes on prospects from the Yankees, Phillies, Jays, and Rangers. And I looked at five potential prospect callups for September. I also held a Klawchat on Thursday.

At Vulture this week, I looked at five major Game of Thrones-themed boardgames, not just reskinned games but several original titles like the excellent GoT Card Game. For Paste, I reviewed the Tour de France-themed boardgame La Flamme Rouge, which is light and good for family play. And here on the dish I reviewed the strong app version of the two-player game Jaipur, a steal at $5.

I’m trying something new this week, and if you find it useful I’d appreciate your feedback. I get a lot of press releases on boardgames from publishers, so I’m including the best of those at the end of this run of links along with boardgame-related news items. These will include Kickstarter announcements that look interesting to me, and if I’ve seen a game at all I’ll indicate it in the blurb.

This is your regular reminder that my book Smart Baseball is available everywhere now in hardcover, e-book, and audiobook formats. Also, please sign up for my free email newsletter, as my subscriber count is down one after I removed that one guy who complained about the most recent edition and called me a “tool.”

And now, the links…

Filed Under: Uncategorized Tagged With: , , , , , , , ,
→ June 15, 2015
→ By

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.

Filed Under: Uncategorized Tagged With: , , , ,
→ August 16, 2010
→ By

Prime Obsession.

I admit it: I am not afraid of math.

And if you’re not afraid of math either – in this case, some fairly heavy math – you might enjoy Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics as much as I did. It’s a book about an obscure question in the field of number theory, one that remains unsolved after 150 years and probably has little to no practical application, but John Derbyshire manages to give the subject some real personality while doing his best to make it accessible to readers who haven’t taken a lot of advanced math classes or who, like me, are a good 13 years removed from their last one.

The subject of Prime Obsession is the Riemann Hypothesis, which states that the non-trivial zeros of Riemann’s zeta function are half part real. “Non-trivial zeros,” in this case at least, are complex numbers (a + bi, where i is the imaginary number defined as the square root of negative 1 and b is nonzero) that give the result of 0 when plugged into the zeta function. “Half part real” means that a in that complex number is equal to ½.

The zeta function is the crux of the matter, the sum of the following infinite series:

That is:

Riemann posed his hypothesis when studying the Prime Number Theorem, which states that for any random number N, the probability of N being prime (and thus the frequency of primes around N) is roughly equal to the reciprocal of the natural logarithm of N, that is, 1/ln(N). In his one paper on the subject, he hypothesized that the frequency of primes and the differences between the actual frequency and the predicted frequency in the Prime Number Theorem was connected to the zeros of this zeta function. He couldn’t prove it at the time, and even though David Hilbert declared it one of the great mathematical problems of the 20th century in 1900, one of a list that has seen all but two of its number* solved, and in 2000 the Riemann Hypothesis was named one of the Millennium Prize Problems by the Clay Mathematics Institute, it remains unsolved. Prove or disprove it and you’ll get a cool million bucks for your trouble.

As you might imagine, solving the problem isn’t easy; indeed, it stands unsolved more than a decade after Sir Andrew Wiles’ solution of the equally perplexing problem of Fermat’s Last Theorem, one that required the development of an entire new field of mathematics (topology) unknown to Fermat at the time that he wrote that he had a “truly marvelous proof” to the problem. (Current thought is that whatever proof he had was incomplete.) The difficulty of proving or disproving the Riemann Hypothesis has led many of the major figures in mathematics, particularly in number theory, to attempt to tackle all or part of the problem or to work on further theorems and conjectures that build on the assumption that the “RH” is true. (And it has at least held true so far for very large numbers, which is not a proof but is weak evidence in its favor.)

Derbyshire’s main difficulty, beyond the lack of a clear resolution to the story, is making the solution of a potentially useless mathematical conundrum interesting; Wiles’ proof of Fermat’s Last Theorem was momentous and newsworthy, but the practical applications have been nil – it’s merely interesting to people who like numbers. Proving the Riemann Hypothesis would likely have a similar lack of real-world effects, and the hypothesis itself is a lot harder to grasp than Fermat’s Last Theorem was; the latter problem had an incredibly complex solution, but the question itself was easy for anyone who’d taken algebra to understand. Derbyshire does a masterful job of walking through the history of the Riemann Hypothesis, from earlier work on prime numbers, including the PNT, through Riemann’s brief life and career in mathematics to the major developments in the 151 years since his seminal paper appeared.

The book alternates between chapters walking through the math and chapters on the history and personalities involved in the hypothesis’ history. Carl Friedrich Gauss has a starring role early, while G.H. Hardy, Leonhard Euler, J.E. Littlewood, Jacques Hadamard, and Hilbert appear at some length later on. Derbyshire sprinkles stories of their peculiarities, senses of humor, and non-mathematical interests to keep the text lighter while also highlighting the chance occurrences that made some of the progress on the proof possible and regularly pointing out the remarkable longevity of most of the major mathematicians he mentions.

His math writing, while clearly geared to a lay audience, still got fuzzy for me when he got deeper into the zeta function as he tried to map it to the complex plane. Derbyshire relies on these “visual” interpretations that don’t correspond to any sort of plane or graphs that I’ve seen elsewhere, and I felt it was the one time he presupposed some familiarity with higher math on the part of the reader. But to his credit, he relies largely on algebra and gives a brief (re-)introduction to differentiation and integration for the short periods where calculus is necessary to move the math story forward. He also hits many major touchstones that will unlock memories for those of you who took and enjoyed lots of math classes, from the Sieve of Eratosthenes to the amazing Euler’s Identity, the latter of which states that

And if you look at that formula and are amused, fascinated, or just generally intrigued, Prime Obsession is a book for you.

I also recommend a book about one of the mathematicians who makes a cameo appearance in Derbyshire’s book, The Man Who Loved Only Numbers: The Story of Paul Erd?s and the Search for Mathematical Truth. Erd?s was a Hungarian-born savant who lived most of his life out of a suitcase, traveling the world, arriving at the doors of mathematicians he knew and announcing that “my brain is open,” after which he’d settle in for a few days or weeks and embark with his host on a streak of problem-solving and paper-writing. He had his own peculiar vocabulary, consumed large quantities of caffeine and later amphetamines, and combined brilliance and prolificacy (that’s peak and longevity for you Hall of Fame watchers) to the point where other mathematicians are referred to by their “Erd?s number,” where a person who co-authored a paper with Erd?s has an Erd?s number of one, while others are marked by how many papers you must go through to create the shortest possible chain back to Erd?s.

Filed Under: Uncategorized Tagged With: , , , , ,