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

  • Toyota, Subaru recall EVs because tires might literally fall off
    Toyota says 'all of the hub bolts' can loosen even 'after low-mileage use'

    Toyota and Subaru are recalling several thousand electric vehicles that might spontaneously shed tires due to self-loosening hub bolts. 

    Toyota issued the recall last week for 2023 bZ4X all-electric SUVs, 2,700 of which are affected, the automaker said. Subaru is recalling all-electric Solterras, which were developed jointly with Toyota and have the same issue, Reuters reported.

    Japan's auto safety regulating body said "sharp turns and sudden braking could cause a hub bolt to loosen," Reuters said, though it's unknown if any actual accidents have been caused by the defect. In its recall notice, Toyota said "all of the hub bolts" can loosen "after low-mileage use," but said it was still investigating the cause of, and driving conditions that can lead to, the issue. 

    Continue reading
  • Alcatel-Lucent Enterprise adds Wi-Fi 6E to 'premium' access points
    Company claims standard will improve performance in dense environments

    Alcatel-Lucent Enterprise is the latest networking outfit to add Wi-Fi 6E capability to its hardware, opening up access to the less congested 6GHz spectrum for business users.

    The France-based company just revealed the OmniAccess Stellar 14xx series of wireless access points, which are set for availability from this September. Alcatel-Lucent Enterprise said its first Wi-Fi 6E device will be a high-end "premium" Access Point and will be followed by a mid-range product by the end of the year.

    Wi-Fi 6E is compatible with the Wi-Fi 6 standard, but adds the ability to use channels in the 6GHz portion of the spectrum, a feature that will be built into the upcoming Wi-Fi 7 standard from the start. This enables users to reduce network contention, or so the argument goes, as the 6GHz portion of the spectrum is less congested with other traffic than the existing 2.4GHz and 5GHz frequencies used for Wi-Fi access.

    Continue reading
  • Will Lenovo ever think beyond hardware?
    Then again, why develop your own software à la HPE GreenLake when you can use someone else's?

    Analysis Lenovo fancies its TruScale anything-as-a-service (XaaS) platform as a more flexible competitor to HPE GreenLake or Dell Apex. Unlike its rivals, Lenovo doesn't believe it needs to mimic all aspects of the cloud to be successful.

    While subscription services are nothing new for Lenovo, the company only recently consolidated its offerings into a unified XaaS service called TruScale.

    On the surface TruScale ticks most of the XaaS boxes — cloud-like consumption model, subscription pricing — and it works just like you'd expect. Sign up for a certain amount of compute capacity and a short time later a rack full of pre-plumbed compute, storage, and network boxes are delivered to your place of choosing, whether that's a private datacenter, colo, or edge location.

    Continue reading
  • Intel is running rings around AMD and Arm at the edge
    What will it take to loosen the x86 giant's edge stranglehold?

    Analysis Supermicro launched a wave of edge appliances using Intel's newly refreshed Xeon-D processors last week. The launch itself was nothing to write home about, but a thought occurred: with all the hype surrounding the outer reaches of computing that we call the edge, you'd think there would be more competition from chipmakers in this arena.

    So where are all the AMD and Arm-based edge appliances?

    A glance through the catalogs of the major OEMs – Dell, HPE, Lenovo, Inspur, Supermicro – returned plenty of results for AMD servers, but few, if any, validated for edge deployments. In fact, Supermicro was the only one of the five vendors that even offered an AMD-based edge appliance – which used an ageing Epyc processor. Hardly a great showing from AMD. Meanwhile, just one appliance from Inspur used an Arm-based chip from Nvidia.

    Continue reading
  • NASA's Psyche mission: 2022 launch is off after software arrives late
    Launch window slides into 2023 or 2024 for asteroid-probing project

    Sadly for NASA's mission to take samples from the asteroid Psyche, software problems mean the spacecraft is going to miss its 2022 launch window.

    The US space agency made the announcement on Friday: "Due to the late delivery of the spacecraft's flight software and testing equipment, NASA does not have sufficient time to complete the testing needed ahead of its remaining launch period this year, which ends on October 11."

    While it appears the software and testbeds are now working, there just isn't enough time to get everything done before a SpaceX Falcon Heavy sends the spacecraft to study a metallic-rich asteroid of the same name.

    Continue reading
  • Rise in Taiwanese energy prices may hit global chip production
    National provider considering cost increase of 8%, which could be passed on to tech customers

    Taiwan's state-owned energy company is looking to raise prices for industrial users, a move likely to impact chipmakers such as TSMC, which may well have a knock-on effect on the semiconductor supply chain.

    According to Bloomberg, the Taiwan Power Company, which produces electricity for the island nation, has proposed increasing electricity costs by at least 8 percent for industrial users, the first increase in four years.

    The power company has itself been hit by the rising costs of fuel, including the imported coal and natural gas it uses to generate electricity. At the same time, the country is experiencing record demand for power because of increasing industrial requirements and because of high temperatures driving the use of air conditioning, as reported by the local Taipei Times.

    Continue reading

Biting the hand that feeds IT © 1998–2022