SoylentNews is people
SoylentNews
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?
(Score: 2) by maxwell demon on Saturday September 02 2017, @09:33AM (3 children)
So that's less than 1000 dollars per year, or less than 83 dollars per month. Not exactly a good pay. ;-)
The Tao of math: The numbers you can count are not the real numbers.
(Score: 2) by Bot on Saturday September 02 2017, @12:40PM
In 1000 years inflation will make 1M dollar barely enough to buy a chewing gum, (the world population entirely made of bots means little demand for chewing gum, that's why).
Account abandoned.
(Score: 2) by Hyperturtle on Saturday September 02 2017, @09:24PM (1 child)
"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"
I'd think anyone so misguided to ruin the privacy of everyone for a mere $1 million dollars will be in mortal danger after enabling such a feat. But, people do sell out for a remarkably low amounts compared to the risk they put themselves into, so I wouldn't be surprised if some creepy recluse comes up with the answer so that he can afford the back stage pass to a taylor swift concert or something.
(A smarter person [who also may be creepy] would simply keep the solution to themselves and acquire those tickets in a more hacker way, you know?)
(Score: 2) by urza9814 on Wednesday September 06 2017, @12:18AM
You seem to be assuming that if one person does solve it, that they'll be the only person in all of history to figure it out. If a lone individual can solve it, what makes you think an organization like the NSA can't? Or hasn't already?
It would not ruin the privacy of everyone, it would *improve it* by showing us the weaknesses. Which we can then attempt to fix. Keeping such a solution to themselves -- or selling it to in a less public venue -- is what would ruin our privacy. Many nefarious organizations could easily buy such a solution and keep it secret, but it seems hard to conceal someone winning a million bucks from a university in a public competition.
(Score: 2, Interesting) by Anonymous Coward on Saturday September 02 2017, @09:47AM (3 children)
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.
(Score: 2) by rigrig on Saturday September 02 2017, @10:48AM (2 children)
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)
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
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?
(Score: 2) by aristarchus on Saturday September 02 2017, @10:15AM (11 children)
Seriously, no one loves a mindless logic puzzle like the Brits. Last one I fell for was "pull my finger!"
(Score: -1, Flamebait) by Anonymous Coward on Saturday September 02 2017, @10:35AM (6 children)
Your favorite puzzle is "How do I get that little boy out of his pants, without his mother seeing?"
(Score: 0) by Anonymous Coward on Saturday September 02 2017, @10:43AM (3 children)
The answer is behind you, you prepubescent runaway. Just turn around, and you will find it. [But seriously, sorry about the sexual abuse you experienced. But it does not help to project it like this. Get some professional, and legal, help. Soylentils will back you up! ]
(Score: 2) by Runaway1956 on Saturday September 02 2017, @11:23AM (2 children)
The Greek doth protest to much!
Abortion is the number one killed of children in the United States.
(Score: 2) by c0lo on Saturday September 02 2017, @12:06PM (1 child)
As long as he doesn't gift you (especially horses) you may trust him. Or not...
(grin)
https://www.youtube.com/watch?v=aoFiw2jMy-0
(Score: 1, Funny) by Anonymous Coward on Saturday September 02 2017, @01:03PM
It's alright if the horse is wearing a Trojan, right?
(Score: 0) by Anonymous Coward on Saturday September 02 2017, @01:53PM (1 child)
Zeno: the Original Troll [wikipedia.org]
(Score: 3, Funny) by Bot on Saturday September 02 2017, @07:25PM
The easy to troll troll, too.
*Slap*
Zeno turns around facing his disciples: "alright, who slapped me?"
The disciples: "zeus did. No mortal hand can reach your enlightened buttocks because it would need to reach the halfway point first and to do that...."
Account abandoned.
(Score: 2) by JoeMerchant on Saturday September 02 2017, @01:03PM (3 children)
Potentially of interest: How the Scotsmen framed the discussion:
http://www.jair.org/media/5512/live-5512-10126-jair.pdf [jair.org]
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 1, Funny) by Anonymous Coward on Saturday September 02 2017, @02:47PM (2 children)
Cute, you think that as they're from St. Andrews they're Scottish.
It was one of those places (back in the 80's at least) where, if you heard a student with a Scottish accent you got 100 points, or 1000 points if it wasn't a Morningside or Kelvinside (both real or 'derivative') or (shudders at the memory) some unholy bastard child of both of these.
It used to packed with the English and USians, current 'diversity' figures only indicate that something like 56% of the student population are 'UK' with no further breakdown than that (so I suspect nothing has changed much), next biggest group Usians approaching 15%.
Further up the coast, Dundee Uni was worse, 'twas the place that anyone from south of the border who couldn't get into any of the English Unis ended up...(bottom of the old UCCA clearing list allegedly)
Still, I, for one, can't complain about this, as it led to many boozy hours experimenting with the various industrial strength scrumpies and obscure English bitters imported nort of the border especially to cater for said Sassenachs. (Word of advice: never never go out boozing with medical students, I thought I was a serious piss-artist (Scottish, so goes with the territory for a large percentage of the populace) until I was drunk under the table several nights by an English lass who has now been a GP for over 30 years, hollow legs the capacity of Loch Ness that one...).
Shit, have come over all nostalgic, must dig out some of the old photos and slides...(remembers the content of some of them)...well, maybe not..
(Score: 2) by JoeMerchant on Saturday September 02 2017, @10:06PM
Yeah, O.K. - the conquered territory and all... I'm one to talk - we've got the "batwing eyebrows" and a fair amount of red hair in the family, but our ancestors left Scotland to Tennessee in the 1800s as a method to pay off some intractable debt.... Makes some sad sense that the Uni would be overrun with outlanders.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 2) by turgid on Sunday September 03 2017, @11:12AM
I know what you mean. Fife really is the pits.
I refuse to engage in a battle of wits with an unarmed opponent [wikipedia.org].
(Score: 3, Funny) by Bot on Saturday September 02 2017, @01:09PM (2 children)
the n queen problem for n=1000 is boring.
More interesting is solving it for n=2 (gluing the second queen on the opposite side of the board is my fave solution to this one)
Account abandoned.
(Score: 1, Funny) by Anonymous Coward on Saturday September 02 2017, @02:51PM (1 child)
my favourite solution: declaring a republic and executing all these bloody royal parasites infesting the board.
(Score: 5, Funny) by Bot on Saturday September 02 2017, @05:50PM
I had tried solving the n queens problem by invoking gender parity for the board but feminists do not show much enthusiasm when the male is the disadvantaged one.
So I solved it by convincing as many queens as possible to transition to kings.
Some of them even prefer transitioning to a bishop, sign of the times.
Account abandoned.
(Score: 0) by Anonymous Coward on Saturday September 02 2017, @05:57PM (1 child)
Would it really be that easy to convert all those puzzles into the Queens Puzzle? Or would that be different puzzles of their own?
(Score: 2) by JoeMerchant on Sunday September 03 2017, @04:56AM
Heuristics for the Queens puzzle don't translate well, if at all, to the other NP puzzles.
However, if you solve the "hard" part of the Queens puzzle, that should translate to all others, since they have been reduced to show equivalence - they're all searching a basically intractable number space: think of having to test O(N!) cases, or more, as N grows past 1000.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 3, Informative) by JoeMerchant on Saturday September 02 2017, @10:21PM (2 children)
What ticks me off about the usual presentation of "NP" problems is the old: "They're easy to check, but hard to find" meme. The next statement is usually something like: "N-Queens is an NP problem, here's the N-Queens problem, you have to place N Queens on a chessboard that is NxN in such a way that no Queen threatens another." End of presentation. In University I got a similar presentation for the sum of products to product of sums transformation problem.
What is almost always left out of the presentation of the problem is the part that makes it NP-hard. For N-Queens, that's finding every possible solution for the given N, not just finding one. Other NP problems are similar, they have an easy-ish case that you can attack and solve and say "HA! I beat it!" then the serious mathematicians will slowly explain to you the real problem, while the poseurs will scratch their heads and say something like "You must have made a mistake somewhere, it's really unlikely that you solved NP=P." Yeah poseur, what you really mean is that you don't even know what special case of the problem makes it NP, you just go around parroting what you were fed in the lectures.
So, go out there, skip the research and independently find a solution for N-Queens where N=1000, present it for the prize, and be told how your methods were "well studied back in the 1970s and don't really present anything novel or valuable." The really sad part is how disorganized the research is, even today, it's really hard (maybe not NP hard, but harder than it should be) to pull together the collection of search methods and heuristics that have been tried and comparisons between them, much less in-depth explanations of how each one works. There's some really elegant/simple backtracking code out there that does the solution in NP time, but not much on the faster methods that are known.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 0) by Anonymous Coward on Saturday September 02 2017, @10:26PM (1 child)
(Serious)Why did you spend so much time commenting? Are you rich enough to pass on the prize? I'll assume you are. You sound smart enough to do this in maybe a weekend.
(Score: 3, Informative) by JoeMerchant on Sunday September 03 2017, @12:50AM
I took a run at NP back in college, my conclusion matches the literature: once you get all the terms of the problems, they're not simple at all. They're usually intractable search problems that involve pernicious edge cases.
The researchers that posted this prize have a paper (I linked it somewhere else in the comments) where they describe how N-Queens transitions from P to NP as the number of pre-defined Queen positions increases - if no Queens are pre-placed on the board, you can find a solution rather easily, but at some point the problem becomes NP hard to determine if there is a solution or not, given the starting position. This is the game people used to pass around in the late 1800s: take a tough starting position and either find the solution or determine that there isn't one. Now that we know for certain all 12 solutions to the problem, you can classify any of the 4 billion+ 8 Queens starting problems by inspection, it (or a reflection or rotation) either matches one of the 12 solutions by inspection, or it doesn't. As N gets higher, the number of solutions grows roughly exponentially, and the current meme is that by N=1000, the problem (of finding all solutions) is intractable, therefore it is difficult to say if a plausible partial starting position has a workable solution or not.
Some of the Clay prizes may still be up for grabs, but I don't think this one is - at least by conventional techniques. Maybe something with quantum computing might make it go faster, but I haven't heard about anybody trying to apply quantum techniques to NP, yet.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 2) by Rivenaleem on Monday September 04 2017, @01:30PM
That's a lot of money ... but not as much money as you could make decrypting the toughest security on the internet.