THE
tech
I SS U E
solving the
big problems
Eugene’s Matt Ginsberg just wants life to be interesting
BY B O B K E E F E R
“ I
nformation,” 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
M AT T G I N S B E R G
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.” ■
eugeneweekly.com • A ugust 23, 2018
13