20 April 2019 | NewScientist | 15NEWS & TECHNOLOGY
Jacob AronONE of the biggest open problems
in mathematics may be solved
within the next decade, according
to a poll of computer scientists.
A solution to the “P versus NP”
problem is worth $1 million to
whoever finds it – and potentially
much more to the world at large.
The problem is a question about
how long algorithms take to run
and whether some seemingly
hard mathematical problems are
actually easy to solve. P and NP
both represent groups of
mathematical problems, but
it isn’t known if these groups
are actually identical.
P, which stands for polynomial
time, consists of problems that
can be solved by an algorithm in
a relatively short time. NP, which
stands for nondeterministic
polynomial time, comprises
problems that are easy to check
if you have the right answer given
a potential candidate, although
actually finding an answer in the
first place might be difficult.
NP problems include a numberof important real-world tasks,
such as the travelling salesman
problem, important in logistics,
which involves finding a route
between a list of cities that is
shorter than a certain limit.
Given such a route, you can easily
check if it fits the limit, but
finding one is more difficult.
The P versus NP problem asks
whether these two collections
of problems are actually the same.
If they are, and P = NP, then the
implications are potentially
world-changing, because it could
become much easier to solvethese tasks. If they aren’t, and
P doesn’t equal NP, a proof would
still answer basic questions about
the nature of computation.
The problem was first stated
in 1971 and has since become
one of the most important
open questions in mathematics.
Anyone who can find the answereither way will receive $1 million
from the Clay Mathematics
Institute in New Hampshire.
William Gasarch at the
University of Maryland conducts
polls of his colleagues to gauge
the current state of the problem.
His first poll, in 2002, found that
just 61 per cent of respondents
thought P ≠ NP. In 2012, that rose
to 83 per cent, and now, in 2019,
it has slightly increased to 88 per
cent. Support for P = NP has also
risen, however, from 9 per cent
in 2002 to 12 per cent in 2019, with
a decrease in the “don’t knows”.
Confidence we might soon have
an answer is also rising. In 2002,
just 5 per cent thought P versusNP would be resolved in the next
decade. Now the figure is 22 per
cent. “If anything, I think that as
the problem remains open longer,
it seems harder,” says Gasarch.
There was little agreement
on the kind of mathematics that
would ultimately be used to solve
the problem, although a number
of people suggested that artificial
intelligence could play a role.
“As this poll demonstrates,
there is no consensus on how
this problem will be eventually
solved,” says Neil Immerman at
the University of Massachusetts,
Amherst. “For that reason, it is
hard to measure the progress
we have made since 1971.” ■A million-dollar
maths problem
WESTMACTODAY, many flowers make nectar
to attract pollinating insects. But a
reanalysis of a Jurassic fly suggests
that pollinators may have existed long
before Earth’s first flowers bloomed.
Alexander Khramov and Elena
Lukashevich of the Borissiak
Palaeontological Institute in Moscow,
Russia, have been studying a fossil
specimen of Archocyrtus kovalevi,
a late Jurassic fly, found in Kazakhstan
and first described in 1996.
When they examined the long,Nectar-loving
fly lived before
flowers existed
straight structure lying underneath
the fly’s body, they realised it wasn’t
a piece of vegetation, as previously
assumed, but a part of the fly. The
structure isn’t enriched in carbon,
as would be expected for vegetation,
and has what looks like a food canal
running through it.
They report that A. kovalevi was
about a centimetre in length, with a
drinking straw-like proboscis nearly
twice as long as its body. As it doesn’t
have any piercing structures, Khramov
says the proboscis was probably for
sucking nectar, not blood (Gondwana
Research, doi.org/c4fh).
But at about 160 million years old,
the fly predates the emergence of
angiosperms, the group of floweringplants, by more than 40 million years.
“Finding a fossil insect of that age
with such a wonderfully long
proboscis is like finding a caveman
with an AK-47,” says Khramov.
Khramov thinks A. kovalevi’s giant
straw was for reaching into the cones
of gymnosperms, the group of plants
that includes conifers. One candidate
is Bennettitales, a now-extinct type
of plant with almost flower-like cones
that may have lured pollinators with
hidden sugar drops.
“For that time and place, members
of Bennettitales are the most logical
host plant for this fly,” says Carol
Hotton at the Smithsonian National
Museum of Natural History in
Washington DC. Jake Buehler ■“First stated in 1971, the
problem has become one
of the most important
questions in mathematics”Archocyrtus kovalevi may have drunk
nectar from Jurassic flower-like conesDMITRY^ BOGDA
NOV