“Information,” Matt Ginsberg says, “is stored in my head in a slightly odd way.”
We’re sitting outside at Starbucks near Valley River Center on a bright summer morning. I’ve known Ginsberg casually for years in a very narrow context: He is a constructor of crossword puzzles that appear in The New York Times. Now, I’ve called him up to find out more.
It turns out Ginsberg is a kind of Renaissance man of computing. He’s the head of a successful artificial intelligence software firm. A thin, high-intensity man of 63, he studied and has taught at Oxford and taught at Stanford. He is a novelist. He built and flies his own airplane.
“I realized one day,” he says, “that my life’s goal is to be interesting. I don’t care much about money or fame. I just want to be interesting.”
Ginsberg was about 13 years old when he encountered a computer for the first time. “My cousin-once-removed worked for a brokerage house in New York City,” he says. “I was able to write a little program on punch cards and run it on a Saturday. And that was it.”
In high school he wrote programs in BASIC, the simple programming language of the 1960s and ’70s, that did such things as parse sentences, using concepts from Noam Chomsky, and determine whether a given number was a prime. He souped up an early computer game he liked, to make it more exciting.
“And I tried to write a chess-playing program,” he says. “But that was too hard for me.”
These days Ginsberg does his computing on a bigger playing field. A program he devised helps the U.S. Air Force save money by picking fuel-efficient routes for all its non-combat flights.
An unusually wide-ranging thinker, Ginsberg has applied himself to a wide range of problems and has an interesting array of contacts outside the tech world. He is on a first name basis with The New York Times’ famous crossword editor Will Shortz. He’s been written about in the Times and on the data-wonk site fivethirtyeight.com.
He recently was working with his son on a hardware-software device that, using an array of video cameras, could call whether a basketball shot attempted from any point on the court was going to score or not, or whether a volleyball serve would be in. The call would come well before the actual event. He had interest from Mark Cuban, owner of the Dallas Mavericks
The project, though, missed its goal. Ginsberg is good with programming, but is less adept at sports politics. He had been working with the University of Oregon women’s volleyball team. “The NCAA found out we were doing this and their heads exploded,” he says. “We asked, ‘What rule does it violate?’
“‘We don’t know,’ they said. ‘And we don’t care.’”
Ginsberg sighs. “I can see their perspective.”
When he was 24, Ginsberg got a doctorate in astrophysics from Oxford University. After working in a field that relied on abstract concepts of quantum thermodynamics, he came to a realization. “I decided I wanted to do something that mattered,” he says.
He decided to move into artificial intelligence. At that point AI meant one place: Stanford University. He taught there 10 years.
Perhaps the biggest problem Ginsberg has ever taken on is usually written in algebraic form:
P = NP
The question of whether P = NP is (Google it!) a major unsolved problem in computer science — perhaps the unsolved problem.
In brief, the question it poses is this: If you can, in a reasonably short amount of time, prove whether a proposed solution to a problem is correct, does that mean that the problem can be solved in a similarly short amount of time?
“If P = NP, it would mean that pretty much any problem that God can solve, we can solve,” Ginsberg says on his website. “We could break any code, whether it’s the computer code that Amazon uses to store your credit card information, or the genetic code that predetermines how likely you are to get heart disease or cancer.”
P = NP is one of seven problems that The Clay Mathematics Institute has offered a $1 million reward for solving. Its solution would have implications for not just math and computer science but for such diverse fields as cryptography, economics, philosophy — in short, for just about everything.
“P = NP is the most interesting unsolved problem in computing,” Ginsberg says. “I don’t think anything else is close.”
Most mathematicians believe that P does not = NP. There are problems, in other words, that are simply unsolvable, even though we can recognize their solutions when we stumble across them.
Ginsberg can be cantankerous on this and other issues. (In a column in The Register-Guard he once, for example, called on the entire Eugene school board to resign.) So, perhaps not surprisingly, he is one of the few who believe the majority of mathematicians are wrong.
Ginsberg firmly believes that P = NP. He just can’t prove it — yet.
“I believe that P=NP because (a) no one has proven it either way, but a lot more people have failed to prove that they are unequal than have failed to prove that they are equal, (b) we seem to be able to solve almost anything in practice, and (c) I don’t believe that God would put this particular barrier between our abilities and His,” Ginsberg explains in an email. Yes, he is religious.
“Alternatively, for those who argue that anyone can recognize a mathematical proof but it takes a genius like [mathematician Johann Carl Friedrich] Gauss to produce one, I would argue that Gauss and a normal schmo are basically identical from a hardware perspective in any case.”
Ginsberg has even written and published a novel about the problem. His 2018 thriller Factor Man, which has a five-star rating on Amazon with 42 reviews, imagines what would happen if someone — a mysterious figure who goes by the name Factor Man — proves that P = NP, leading to a certain amount of chaos in world financial markets and politics.
Factor Man took him just six months to write. “I tried to imagine a world where someone proved that P=NP, and then said what was going to happen,” he says.
Characters in the book include a number of real-life people, from Shortz to fivethirtyeight.com’s Nate Silver and even, thinly disguised, Ginsberg himself.
But back to the way Ginsberg’s brain works. He can create crossword puzzles with the best of them. He’s written a computer program, Dr. Fill, that can solve the New York Times Saturday crossword, the toughest of the week, in minutes.
But Ginsberg himself can’t solve crossword puzzles at all. His mind doesn’t easily free associate. “When my puzzles come out I can’t do them,” he says. “My brain doesn’t work that way. I admit it. I knew this in college.”
Comments are closed.