The Experts Weigh In
In 2002, William Gasarch took a poll of a hundred leading experts in this
area, asking the question whether the class P of problems solvable in
polynomial time was equal to the class NP of Cook’s tough cookies. The
envelope, please.^4
Sixty-one voted that P NP (no polynomial-time algorithm exists for
any tough cookie).
Nine voted for P NP.
Four thought that it was an undecidable question in ZFC!
Three thought that it could be resolved by demonstrating an explicit
way to solve one of the tough cookies in polynomial time, rather
than merely showing an algorithm must exist.
Twenty-two respondents wouldn’t even hazard a guess.Gasarch also asked the respondents to estimate when the problem would
be solved. The median guess was in 2050, almost forty-eight years after
the poll was taken.
Here are a couple of views from the two opposing camps.
Bela Bollobas: 20 20, PNP. “I think that in this respect I am on the
loony fringe of the mathematical community. I think (not too strongly)
that PNP and this will be proved within twenty years. Some years ago,
Charles Read and I worked on it quite a bit, and we even had a celebra-
tory dinner in a good restaurant before we found an absolutely fatal
mistake. I would not be astonished if very clever geometric and combi-
natorial techniques gave the result, without discovering revolutionary
new tools.”
Richard Karp: PNP. “My intuitive belief is that P is unequal to NP, but
the only supporting arguments I can offer are the failure of all efforts to
place specific NP-complete problems in P by constructing polynomial-
time algorithms. I believe that the traditional proof techniques will not
suffice. Something entirely novel will be required. My hunch is that the
problem will be solved by a young researcher who is not encumbered by
too much conventional wisdom about how to attack the problem.”
Notice that one person feels that standard methods suffice, while the
other feels that it will require someone who can “think outside the box.”
I’d vote for the latter; my impression of the history of difficult problems is
that many more of them seem to succumb to new approaches rather than
to pushing current ideas as far as they will go.
166 How Math Explains the World