That virtually impossible classic compsci P vs NP problem is virtually impossible, say boffins

$1m prize is still up for grabs if you want to prove them wrong

Frustrated accountant puts head in hands. Photo by Shutterstock

A trio of computer scientists from the University of St Andrews in Fife, Scotland, has published results showing that a classic chess puzzle dating back 150 years is so computationally taxing that it could take thousands of years to solve.

It’s a crushing blow for those trying to win the $1m prize offered for cracking the problem by the Clay Mathematics Institute in Peterborough, New Hampshire, a non-profit US organization that supports mathematical research.

A paper published in the Journal of Artificial Intelligence Research describes the n‑Queens completion problem. It might be easy to understand, but it’s very difficult to solve in a practical sense. The goal is to place n queens on an n by n chessboard in a way that no two queens are ever on the same row or column, or diagonal to each other.

A simpler version of the conundrum was introduced in 1850. Players had to devise a method to put eight queens on a standard chessboard, measuring eight by eight squares, so that no two queens could ever be in a position to attack one another.

It can be solved by putting a queen in each row so that no two queens are ever in the same column, or diagonal from one another. The solution can be found for all n except 2 and 3, but once n goes beyond 1,000 it becomes increasingly difficult to compute using a practical system.

The researchers hope that their paper – which shows the problem is both “NP‑Complete” and “#P‑Complete” – might encourage more people to step up to the challenge. It’s related to the P vs NP problem, a major mystery in computer science that asks if a question whose answer can be quickly checked, can be solved again quickly?

A problem is P‑complete if the solution is easy to find, and NP‑complete if the answer is also easy to check. The paper shows that the n‑Queens problem can be cracked, but not a second time quickly.

Ian Gent, lead author of the paper and a professor of computer science at the University of St Andrews, said: “If you could write a computer program that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily.

“This includes trivial challenges like working out the largest group of your Facebook friends who don’t know each other, or very important ones like cracking the codes that keep all our online transactions safe.”

The researchers found that once the chessboard is larger than 1,000 by 1,000, computers can no longer cope with the monumental number of possible squares in which to place a queen.

There have been hundreds of failed attempts to solve the P vs NP puzzle. German computer scientist Norbert Blum, a researcher at the University of Bonn, proposed a solution earlier this month, but it was recently revealed that his proof was flawed. Blum has since acknowledged his mistakes and retracted his paper on arXiv.

In fact, Peter Nightingale, co-author of the paper and a senior research fellow at the University of St Andrews, believes the problem is impossible.

“Nobody has ever come close to writing a program that can solve the problem quickly," he said. "So what our research has shown is that – for all practical purposes – it can’t be done. There is a $1,000,000 prize for anyone who can prove whether or not the Queens Puzzle can be solved quickly, so the rewards are high.” ®


Biting the hand that feeds IT © 1998–2017