Stories
Slash Boxes
Comments

SoylentNews is people

posted by martyb on Saturday September 02 2017, @09:04AM   Printer-friendly
from the simple!=easy dept.

Researchers at the University of St Andrews have thrown down the gauntlet to computer programmers to find a solution to a "simple" chess puzzle which could, in fact, take thousands of years to solve and net a $1M prize. Computer Scientist Professor Ian Gent and his colleagues, at the University of St Andrews, believe any program capable of solving the famous "Queens Puzzle" efficiently, would be so powerful, it would be capable of solving tasks currently considered impossible, such as decrypting the toughest security on the internet.

Devised in 1850, the Queens Puzzle originally challenged a player to place eight queens on a standard chessboard so that no two queens could attack each other. This means putting one queen in each row, so that no two queens are in the same column, and no two queens in the same diagonal. Although the problem has been solved by human beings, once the chess board increases to a large size no computer program can solve it.

The team found that once the chess board reached 1000 squares by 1000, computer progams could no longer cope with the vast number of options and sunk into a potentially eternal struggle akin to the fictional "super computer" Deep Thought in Douglas Adams' Hitchhiker's Guide to the Galaxy, which took seven and a half million years to provide an answer to the meaning of everything.

https://phys.org/news/2017-09-simple-chess-puzzle-key-1m.html

[Abstract]: "Complexity of n-Queens Completion"

[Source]: https://www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php

Any takers for this challenge?


Original Submission

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 2, Interesting) by Anonymous Coward on Saturday September 02 2017, @09:47AM (3 children)

    by Anonymous Coward on Saturday September 02 2017, @09:47AM (#562888)

    Firstly, humans have only solved small problems, computers have solved larger ones. The article makes it sound as if humans are superior, they aren't.

    Secondly, the link to crypto is bogus. Solving NP complete problems in P doesn't make factoring or discrete logs easy, just P. And P can grow frighteningly quickly.

    Starting Score:    0  points
    Moderation   +2  
       Insightful=1, Interesting=1, Total=2
    Extra 'Interesting' Modifier   0  

    Total Score:   2  
  • (Score: 2) by rigrig on Saturday September 02 2017, @10:48AM (2 children)

    by rigrig (5129) Subscriber Badge <soylentnews@tubul.net> on Saturday September 02 2017, @10:48AM (#562901) Homepage

    Solving NP complete problems in P doesn't make factoring or discrete logs easy, just P. And P can grow frighteningly quickly.

    Isn't the idea that if you have the key decryption is in P, while an attacker needs to solve an NP problem? If those both end up in P your crypto would be either breakable or unusable.

    --
    No one remembers the singer.
    • (Score: 1, Informative) by Anonymous Coward on Saturday September 02 2017, @11:20AM (1 child)

      by Anonymous Coward on Saturday September 02 2017, @11:20AM (#562904)

      Yes and no. Problems in P are considered "easy", but that is only in regards to their computational complexity. Even if a problem is in P, its complexity might still be on the level of, say, n^10000, which is harder to solve than 2^n for small n.

      As an example, let's say that we have two problems on a chessboard of size n by n. One requires precisely n^10000 steps to compute, the other requires 2^n. It is "simpler" to solve the exponentially difficult 2^n problem for a small board of 100x100, since 100^10000 is a number that has 20000 digits -- comparing it with 2^100, which has "only" about 30 digits. Certainly, 2^n is larger than n^10000 for nearly all numbers, although it still takes a while to get there -- for board sizes about 2100210x2100210, the polynomial one becomes "easier". Both would still be intractable by any standards -- although P would eventually become computable if Moore's law still held, You were prepared to wait long enough and the universe had enough atoms for computers.

      • (Score: 2) by bzipitidoo on Saturday September 02 2017, @02:31PM

        by bzipitidoo (4388) on Saturday September 02 2017, @02:31PM (#562926) Journal

        How many problems in P have such large exponents? And, that aren't simply an NP-hard problem that's been converted to P by the cheap trick of simply declaring n to be some constant value, you know, as in 8-queens rather than n-queens?