4 ms·
If 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.
by cperciva 9y ago
If 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.