P vs. NP is a problem at the forefront of computer science. Until now there hasn't been a book written for a general audience that introduces the problem and its importance. Lance Fortnow has authored such a book. Lance I discuss the problem, the book, why he wrote it, and what it takes to write such a book in a way that doesn't scare most of us away. And, we take a few detours into talks about computer science and programming early microcomputers.
About Lance Fortnow
From the author's web-site:
Lance Fortnow is professor and chair of the School of Computer Science of the College of Computing at the Georgia Institute of Technology. His research focuses on computational complexity and its applications to economic theory. He also holds an adjoint professorship at the Toyota Technological Institute at Chicago.
Fortnow received his Ph.D. in Applied Mathematics at MIT in 1989 under the supervision of Michael Sipser. Before he joined Georgia Tech in 2012, Fortnow was a professor at Northwestern University, the University of Chicago, a senior research scientist at the NEC Research Institute and a one-year visitor at CWI and the University of Amsterdam.
Fortnow's research spans computational complexity and its applications, most recently to micro-economic theory. His work on interactive proof systems and time space lower bounds for satsifability have led to his election as a 2007 ACM Fellow. In addition he was an NSF Presidential Faculty Fellow from 1992-1998 and a Fulbright Scholar to the Netherlands in 1996-97.
Among his many activities, Fortnow served as the founding editor-in-chief of the ACM Transaction on Computation Theory, served as chair of ACM SIGACT and currently sits on the Computing Research Association board of directors and the council of the Computing Community Consortium. He served as chair of the IEEE Conference on Computational Complexity from 2000-2006. Fortnow originated and co-authors the Computational Complexity weblog since 2002, the first major theoretical computer science blog. He has thousands of followers on Twitter.
Fortnow's survey The Status of the P versus NP Problem is CACM's most downloaded article. Fortnow has written a popular science book The Golden Ticket: P, NP and the Search for the Impossible loosely based on that article.
About "The Golden Ticket"
From the Princeton University Press web-site:
The P-NP problem is the most important open problem in computer science, if not all of mathematics. Simply stated, it asks whether every problem whose solution can be quickly checked by computer can also be quickly solved by computer. The Golden Ticket provides a nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. In this informative and entertaining book, Lance Fortnow traces how the problem arose during the Cold War on both sides of the Iron Curtain, and gives examples of the problem from a variety of disciplines, including economics, physics, and biology. He explores problems that capture the full difficulty of the P-NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. But difficulty also has its advantages. Hard problems allow us to safely conduct electronic commerce and maintain privacy in our online lives.
The Golden Ticket explores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of this compelling problem.
Mary O'Keeffe has an article in the Albany Area Math Circle blog expanding on some of the discussion in our recent podcast. And, her daughter Catherine created a transcript of the recording. The transcript is annotated with comments that may be of interest to listeners.
Mary's article, Doing justice to describing the work of other math circles that have inspired us elaborates on the contributions and inspiration that Ken Fan and many others have made to help her math circle to thrive.
I'll be interviewing Ken Fan for the "Inspired by Math!" series. And, I plan to seek out the other people who have inspired the folks in the Albany Area and shine the spotlight on those who are willing.
[ Update 4/10/13: An addendum with links to an annotated transcript and to a follow-up article are here. ]
I first learned of Gili's great mathematical community-building work through this wonderful blog article that Mary O'Keeffe wrote. Gili, a high school sophomore, and Mary, professor and founder of the Albany Area Math Circle, have both contributed greatly to making math fun and collaborative. It was a great honor to interview the two. We did the interview on a Friday afternoon right before the two were headed to their weekly Circle.
I'm delighted to have the two in this series as my intention is to share better stories of what math is and can be than what many of us learned in school and these two have a great story.
About Gili and Mary
Gili Rusak is a sophomore in high school who also takes courses in mathematics and computer science at a local college. She has been an active member of the Albany Area Math Circle for five years. She enjoys working with middle school students to enrich their knowledge and love for mathematics. She also volunteers for MathCounts tutoring at a local inner city middle school and is a member of the local Youth Court. In her free time she enjoys mountain biking, running, and other athletics.
Mary O'Keeffe, a public policy economist who studied economics at Harvard (in the same PhD program with Larry Summers!), founded the Albany Area Math Circle in 2001, along with her daughter, Alison Miller, who was then a high school sophomore seeking to build a local community of kindred spirits who shared a passion for collaborating on challenging mathematical problems. Alison went on to many adventures, including the International Math Olympiad, where she became the first American woman to win a gold medal in 2004, and is now a graduate student at Princeton, but the vibrant mathematical community they launched in upstate NY continues to flourish beyond anything they could have envisioned at the outset.
[ Update 4/10/13: An addendum with links to an annotated transcript and to a follow-up article are here. ]
"Math on Trial" is an engaging yet very serious book about how mathematical fallacies can lead to abuse in the courtroom. I had the pleasure of interviewing the mother-daughter team who co-authored the book. They're a very enthusiastic pair who are committed to shining a spotlight on these mathematical errors that wrongly send people to prison.
I hope you enjoy listening to this interview as much as I enjoyed doing it.
About Leila Schneps and Coralie Colmez
Leila Schneps studied mathematics at Harvard University and now holds a research position at the University of Paris, France. She has taught mathematics for nearly 30 years. Schneps's daughter, Coralie Colmez, graduated with a First from Cambridge University in 2009, and now lives in London where she teaches and writes about mathematics. They both belong to the Bayes in Law Research Consortium, an international team devoted to improving the use of probability and statistics in criminal trials.
About "Math on Trial"
From the publisher's web-site:
In the wrong hands, math can be deadly. Even the simplest numbers can become powerful forces when manipulated by politicians or the media, but in the case of the law, your liberty — and your life — can depend on the right calculation.
In Math on Trial, mathematicians Leila Schneps and Coralie Colmez describe ten trials spanning from the nineteenth century to today, in which mathematical arguments were used — and disastrously misused — as evidence. They tell the stories of Sally Clark, who was accused of murdering her children by a doctor with a faulty sense of calculation; of nineteenth-century tycoon Hetty Green, whose dispute over her aunt's will became a signal case in the forensic use of mathematics; and of the case of Amanda Knox, in which a judge's misunderstanding of probability led him to discount critical evidence — which might have kept her in jail. Offering a fresh angle on cases from the nineteenth-century Dreyfus affair to the murder trial of Dutch nurse Lucia de Berk, Schneps and Colmez show how the improper application of mathematical concepts can mean the difference between walking free and life in prison.
A colorful narrative of mathematical abuse, Math on Trial blends courtroom drama, history, and math to show that legal expertise isn't always enough to prove a person innocent.
This podcast is quite different from the previous twenty four. Matthew Watkins and I dive into the sense of wonder and awe that is underneath the mundane experience of math that so many people never get below the surface of. The conversation is deep and a bit mystical at times but I completely agree with Matthew when he claims that the relationship of mathematicians and artists to their subject may not be as different as we imagine.
I absolutely loved Volume 1 of the "Secrets of Creation" trilogy, "The Mystery of the Prime Numbers." I bragged about how it was a remarkable fairy tale for children of all ages in my review here. I've not read volumes 2 and 3 (out soon) but I look forward to devouring them as well.
You might enjoy this email interview that Shecky Riemann did with Matthew Watkins.
Enjoy the podcast!
About Matthew Watkins
Matthew Watkins completed a PhD in mathematics in 1994, but has always been more interested in trying to understand what mathematics "is" and "where it comes from" (as well as trying to explain it to his non-mathematical friends) than pursuing a conventional research or teaching career.
The second half of the 1990s were spent living as a nomadic musician (he plays the saz, a seven-stringed Turkish instrument), contemplating the underlying nature of reality while wandering the British Isles, busking, picking fruit, planting trees, visiting megalithic sites, etc. The music continues, documented here.
In 1999 he had a little maths and physics reference book published (also illustrated by Matt Tweed) as part of the popular Wooden Books series. This has since been licensed by Walker & Co., NYC and last time he checked, it had been translated into at least half a dozen languages.
Since 2000, he's been an Honorary Fellow in Exeter University's mathematics department (which keeps changing its name, but is currently part of the College of Engineering, Mathematics and Physical Sciences). During this time, as well as having done a bit of teaching work, he initiated and has been since been curating the online Number Theory and Physics Archive and the related (but more popularly accessible) site Inexplicable Secrets of Creation, a project which naturally led to the idea of this series of books.
More information is available at Matthew Watkins' homepage.
About the Secrets of Creation
From the trilogy site:
Volume 1, The Mystery of the Prime Numbers (published June 2010) begins by looking at the role of numbers in human cultures, particularly the extent to which they have come to dominate modern Western thinking. If this "number system" is so central to our view of reality, the author suggests, and so many of us give it so little thought, maybe we should have a closer look at it. Prime numbers are then introduced, along with the question everyone seems to ask: "is there a pattern in them?". The issue of what constitutes a pattern is then considered, before the puzzling "splatter" of primes along the number line is explained in terms of the uncoiling of a particularly beautiful spiral. The extent to which the actual arrangement of primes deviates from this "approximate" pattern is examined next, and this "deviation" is revealed to be concealing an infinite collection of wave-like forms. These "waveforms" are carefully explained, again in terms of spirals. In fact, in the absence of a better name (these objects only being of interest to a relatively small band of mathematicians, who communicate in equations), the author has chosen to call them spiral waves. Like a conventional wave (a "sine wave"), they have something like a "frequency". The frequencies of the first handful of spiral waves are presented: a mysterious string of awkward-looking numbers, raising the mind-boggling question where could these particular numbers, lurking within the structure of reality and entirely unknown for almost all of history, possibly have come from?
Information about volumes 2 and 3 can be found at the trilogy site.
Visions of Infinity: The Great Mathematical Problems is Ian Stewart's latest book. Dr. Stewart is one of my heros. I interviewed him for my podcast series and I love his new book. But, I struggled to come up with the right words to write for a review. So, what I've done instead is to take snippets from a number of reviews of the book I found on the web that articulated my own impressions and turned those into a mashup review, followed by a very brief summary of my impressions.
Here's the publisher's description of the book:
For every problem mathematicians solve, another waits to perplex and galvanize them. Such challenges offer a tantalizing glimpse of the field’s unlimited potential, and keep mathematicians looking toward the horizons of intellectual possibility. In Visions of Infinity, celebrated mathematician Ian Stewart explains why these problems exist, what drives mathematicians to solve them, and why their efforts matter in the context of science as a whole. Stewart describes solved problems—like Fermat’s Last Theorem, proved three centuries after it was posited, and the Poincaré Conjecture, cracked by eccentric genius Grigori Perelman—as well as those like the P/NP problem, which could easily remain unproved for another hundred years. An approachable and illuminating history of mathematics as told through fourteen of its greatest problems, Visions of Infinity reveals how mathematicians the world over have risen to meet the challenges set by their predecessors—and how the enigmas of the past inevitably surrender to the powerful techniques of the present.
Below are excerpts from a half dozen reviews on the Web. Keep reading for my impression of the book as bullet points.
To be clear though, while this volume covers some of the most interesting problems in all of mathematics it is NOT a book to draw your non-mathematical friends into the math arena. Even the non-math person who wishes they could like math, and who may have enjoyed Steven Strogatz's "Joy of X," I think will find this particular book too heavy-going. But for the individual already enamored of the subject, and having some familiarity with math's deepest problems, this is a fantastic read. In fact, it's probably my favorite Stewart volume of all the ones I've read.
The four-color map problem can be understood by a bright fourth-grader (the question: whether four colors are enough to ensure that no two countries with a common border share a color). By junior high, most kids can grasp prime numbers and learn something about their properties and patterns. High school algebra students can comprehend what Fermat’s last theorem means. Yet these topics have for decades, or even centuries, occupied the world’s most sophisticated mathematicians.
Capping the discussion is a quick chapter detailing some of the problems that may give mathematicians fits and nightmares into the next century, including quaintly named perfect cuboids, Langton’s Ant, and mysterious constructs called Thrackles. Once again, Stewart delivers an intriguing book that rewards random reading as much as dedicated study.
Stewart’s imaginative, often-witty anecdotes, analogies and diagrams succeed in illuminating many but not all of some very difficult ideas. It will enchant math enthusiasts as well as general readers who pay close attention.
In the end chapters the mathematics gets more “pure” and explanations of the conjectures get more complicated. The reader has to pay more attention. CAUTION: Do not attempt these chapters without possessing full alertness. The chapter “Diophantine Dreams” addresses the search for the proof of the Birch-Swinnerton-Dyer conjecture, where the difficulty won’t just be in finding a proof. It will first be in understanding just what the conjecture is. Make this chapter your own personal Mount Everest.
Just as dynamic systems can "settle down" into chaos/fractals, strange attractors or an oscillation, the book, after taking us on a fascinating journey through the known and unknown, gives us a great, up to date feel for which problems are in which category of difficulty and likely vs. unlikely to be solved in our times. The "toughest" problems are the stuff of cryptanalysis and are "good" from the standpoint of providing security, but Ian also shows the many possible openings at the back of the tent in addition to the door, by suggesting possible "close enough" solutions and directions that are worth pursuing.
The reviews summed up my experience of the book.
- Ian Stewart is a great writer. He is able to weave together mathematics and story to keep the reader's attention and to provide context for why we care about solving these difficult problems.
- I'm not so sure that a motivated high school student can follow all of the ideas. I certainly couldn't. As Shecky points out in my excerpt from his MathTango review (above), "To be clear though, while this volume covers some of the most interesting problems in all of mathematics it is NOT a book to draw your non-mathematical friends into the math arena." Very well said.
- Having hammered in the last point, much of the material in the book is accessible to the motivated student who is willing to focus and persist.
This student from Stanford is awesome! And, in just 8 days his video has gotten over 4 million hits.
Maria and I met a few years ago at a science conference and spent hours sharing our love of sharing math. Maria is starting what I call a "mass math movement." She is changing the story of how infants and toddlers can relate to math. The kickstarter project that launched the Moebius Noodles book is just the beginning. This is very exciting stuff.
About Maria Droujkova
Dr. Maria Droujkova is a curriculum developer and mathematics education consultant. Maria brings together leaders in mathematics education, researchers, developers, parents and teachers for projects and discussions of family mathematics, early algebra, individualized instruction, math games and math clubs.
About Moebius Noodles
In many ways mathematics is like a language: kids need exposure to its richness in early years, so it becomes native to them.
Imagine not talking with babies about anything until they learned the alphabet! This is what happens with math, when babies, toddlers and young kids only ever hear about small numbers and simple shapes.
As parents, we are interested in creating rich, multi-sensory experiences for our children early on. We want to introduce them to the complex and exciting world around them. Yet when it comes to mathematics, we often do just the opposite – simplify, impoverish, limit. Doing this, we are not giving children a chance to observe, play with and ultimately learn math.
The simplistic math is boring not just to children, but to adults as well. The absence of happy familiarity leads to procrastination, frustration, and anxiety when math does come up.
. . .
We are writing an advanced and accessible math book, Moebius Noodles, for young kids and their parents. This book is totally cool! It’s an off-the-beaten-path travel guide to the Math Universe for adventurous families (and it has lots of beautiful pictures, too!) The games in Moebius Noodles draw on these rich properties of everyday objects in ways accessible to parents and kids. If that excites you, become one of the early adopters and help the cause!
I'm experimenting with including some shorter podcasts with the hour-long ones. I discovered Jason Ermer's Collaborative Mathematics Project, was very intrigued by what Jason is up to and got him to do a quick interview.
If you like this interview, these shorter podcasts, or these interviews overall, please leave your comments and please click on the social media links and help spread the word. Thank you!
Erica Klarreich's name came up a couple of times when I asked people who I should interview for the podcast series. So, I looked her up and was impressed with the in depth articles she had written for Scientific American and a number of other publications.
Enjoy this 22nd "Inspired by Math" podcast.
About Erica Klarreich
Adapted from Erica's web-site:
Erica Klarreich has been writing about mathematics and science for a popular audience for more than ten years. A mathematician before she became a full-time journalist, she writes primarily about mathematics, but has also written about a wide range of other scientific fields, including economics, computer science, medicine and biology.
As a freelance journalist based in Berkeley, California, she has written for many publications, including Nature, New Scientist, American Scientist, and Science News, for which she was the mathematics correspondent for several years. She has also served as the Journalist-in-Residence at the Mathematical Sciences Research Institute in Berkeley. Her work has been reprinted in the anthologies The Best Writing on Mathematics 2010 and The Best Writing on Mathematics 2011.