3 ms·
The article completely misinterprets the press release[1]. The University of St Andrews isn't offering a prize; they've just shown that the Queens puzzle on an
by umanwizard 9y ago
The article completely misinterprets the press release[1].
The University of St Andrews isn't offering a prize; they've just shown that the Queens puzzle on an n-by-n board (EDIT: actually, the n Queens completion puzzle) is NP-hard.
(By the way, even the press release, though less wrong than the article, is still pretty bad: apparently NP-complete problems are hard because they use "backtracking". Also it seems to suggest that this is something computer programmers would solve, rather than mathematicians...)
[1]: https://phys.org/news/2017-09-simple-chess-puzzle-key-1m.html#jCp https://phys.org/news/2017-09-simple-chess-puzzle-key-1m.htm...
- cperciva 9y agoIf I'm reading it right, they haven't shown that the N Queens problem is NP-hard, but rather that the N Queens completion problem is NP-hard.
- CJefferson 9y agoYes (one of the authors here), the press release came out very badly. The reference to the Clay prize was to try to demonstrate that lots of people care about solving NP-complete problems in general... N-Queens has long been known to polynomial time (although there is no known efficient way of counting the total number of solutions). We showed N-Queens completion is NP-hard. This is (in my opinion) interesting to people who care about such things, because it's a long standing problem and has the advantage of being easy to explain. However, it is mainly just a curiosity, and provides a new easy way of demonstrating NP-completeness.
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- umanwizard 9y agoYep, sorry, edited my post.
- dang 9y agoOk we'll change the title to that above.
- bandang 9y agosigh. p=np, because https://en.m.wikipedia.org/wiki/Oracle_machine https://en.m.wikipedia.org/wiki/Oracle_machine is a solved problem. although, [ts/sci]. oh well, there goes another account.
- Someone 9y ago'Completely' even is an understatement, given https://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_solutions https://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_s....
- QAPereo 9y agoPhys.org is a dumpster fire, and ANY information from there is better linked to from another source, of which there are many. I recommend the AAAS sites www.eurekalert.com and www.sciencemag.com. As well as Nature. At least then you'll have doi links, and a better class of journalism.