P is not NP? That is the question
One 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 so-called P versus NP problem is worth $1 million and could have a profound effect on computing, and perhaps even the entire world.
The problem is a question about how long algorithms take to run and whether some 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 the 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 number of important real-world tasks, such as the travelling salesman problem, 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 might be more difficult.
Equal or not
The P versus NP problem asks whether these two collections of problems are actually the same. If they are, and P = NP, the implications are potentially world-changing, because it could become much easier to solve these tasks. If they aren’t, and P doesn’t equal NP, or P ≠ NP, a proof would still answer fundamental 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 answer either way will receive $1 million from the Clay Mathematics Institute in Cambridge, Massachusetts.
William Gasarch, a computer scientist at the University of Maryland in College Park, conducts polls of his fellow researchers 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, because the 2002 poll had a large number of “don’t knows”.
Confidence that we might soon have an answer is also rising. In 2002, just 5 per cent thought the problem would be resolved in the next decade, falling to 1 per cent in 2012, but now the figure sits at 22 per cent. “This is very surprising since there has not been any progress on it,” says Gasarch. “If anything, I think that as the problem remains open longer, it seems harder.” More broadly, 66 per cent believe it will be solved before the end of the century.
There was little agreement on the kind of mathematics that would ultimately be used to solve the problem, although a number of respondents suggested that artificial intelligence, not humans, could play a significant role.
“I can see this happening to some extent, but the new idea needed will, I think, come from a human,” says Gasarch. “I hope so, not for any reason of philosophy, but just because if a computer did it we might know that (say) P ≠ NP, but not really know why.”
Neil Immerman at the University of Massachusetts Amherst thinks that this kind of polling is interesting, but ultimately can’t tell us much about the P versus NP problem.
“As this poll demonstrates, there is no consensus on how this problem will be eventually solved,” he says. “For that reason, it is hard to measure the progress we have made since 1971 when the question was first stated.”
For more such insights, log into www.international-maths-challenge.com.
*Credit for article given to Jacob Aron*