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


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.” ®


Other stories you might like

  • Robotics and 5G to spur growth of SoC industry – report
    Big OEMs hogging production and COVID causing supply issues

    The system-on-chip (SoC) side of the semiconductor industry is poised for growth between now and 2026, when it's predicted to be worth $6.85 billion, according to an analyst's report. 

    Chances are good that there's an SoC-powered device within arm's reach of you: the tiny integrated circuits contain everything needed for a basic computer, leading to their proliferation in mobile, IoT and smart devices. 

    The report predicting the growth comes from advisory biz Technavio, which looked at a long list of companies in the SoC market. Vendors it analyzed include Apple, Broadcom, Intel, Nvidia, TSMC, Toshiba, and more. The company predicts that much of the growth between now and 2026 will stem primarily from robotics and 5G. 

    Continue reading
  • Deepfake attacks can easily trick live facial recognition systems online
    Plus: Next PyTorch release will support Apple GPUs so devs can train neural networks on their own laptops

    In brief Miscreants can easily steal someone else's identity by tricking live facial recognition software using deepfakes, according to a new report.

    Sensity AI, a startup focused on tackling identity fraud, carried out a series of pretend attacks. Engineers scanned the image of someone from an ID card, and mapped their likeness onto another person's face. Sensity then tested whether they could breach live facial recognition systems by tricking them into believing the pretend attacker is a real user.

    So-called "liveness tests" try to authenticate identities in real-time, relying on images or video streams from cameras like face recognition used to unlock mobile phones, for example. Nine out of ten vendors failed Sensity's live deepfake attacks.

    Continue reading
  • Lonestar plans to put datacenters in the Moon's lava tubes
    How? Founder tells The Register 'Robots… lots of robots'

    Imagine a future where racks of computer servers hum quietly in darkness below the surface of the Moon.

    Here is where some of the most important data is stored, to be left untouched for as long as can be. The idea sounds like something from science-fiction, but one startup that recently emerged from stealth is trying to turn it into a reality. Lonestar Data Holdings has a unique mission unlike any other cloud provider: to build datacenters on the Moon backing up the world's data.

    "It's inconceivable to me that we are keeping our most precious assets, our knowledge and our data, on Earth, where we're setting off bombs and burning things," Christopher Stott, founder and CEO of Lonestar, told The Register. "We need to put our assets in place off our planet, where we can keep it safe."

    Continue reading

Biting the hand that feeds IT © 1998–2022