The N-Queens completion problem is NP-hard • Hacker News Board

Re: The N-Queens completion problem is NP-hard

#11

Post by chch » Mon, Sep 04, 2017, 4:32 PM UTC

anonetal wrote: post #2

The million-dollar prize just appears to be the Clay Institute's prize for solving P vs NP. I am guessing that the queens problem (a special case of maximum independent set in a graph) is NP-Hard.

If you click through to the "release from the university" on phys.org[1], then the paper itself is listed at the bottom[2], though without a hyperlink. Via the abstract [3]:

> "The n-Queens problem is to place n chess queens on an n by n chessboard so that no two queens are on the same row, column or diagonal. The n-Queens Completion problem is a variant, dating to 1850, in which some queens are already placed and the solver is asked to place the rest, if possible. We show that n-Queens Completion is both NP-Complete and #P-Complete."

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

[2] Quote: "More information: Complexity of n-Queens Completion. Journal of Artificial Intelligence Research. DOI: DOI: 10.1613/jair.5512 , http://jair.org/papers/paper5512.html "

[3] http://jair.org/papers/paper5512.html

Re: The N-Queens completion problem is NP-hard

#12

Post by School-Cotton » Mon, Sep 04, 2017, 4:34 PM UTC

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.htm...

Re: The N-Queens completion problem is NP-hard

#13

Post by cperciva » Mon, Sep 04, 2017, 4:38 PM UTC

School-Cotton wrote: post #12

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 s…

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.

Re: The N-Queens completion problem is NP-hard

#14

Post by anonetal » Mon, Sep 04, 2017, 4:38 PM UTC

cropsieboss wrote: post #7

anonetal wrote: post #2

The million-dollar prize just appears to be the Clay Institute's prize for solving P vs NP. I am guessing that the queens problem (a special case of maximum independent set in a graph) is NP-Hard.

Damn it. I didn't know it's NP hard. I thought I would discover the generating function for the number of possible solutions for board sized N.

Actually the queens problem starting with an empty board is not NP-Hard. See: https://cstheory.stackexchange.com/questions/12682/is-the-n-...

The "completion" problem is the NP-Hard one. As one of the other comments noted, the paper behind this press release is about the completion problem.

Re: The N-Queens completion problem is NP-hard

#15

Post by CJefferson » Mon, Sep 04, 2017, 4:43 PM UTC

cperciva wrote: post #13

School-Cotton wrote: post #12

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 s…

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.

Yes (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.

Re: The N-Queens completion problem is NP-hard

#16

Post by [deleted] » Mon, Sep 04, 2017, 4:47 PM UTC

CJefferson wrote: post #15

cperciva wrote: post #13

Earlier quoted context omitted.

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.

Yes (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 peo…

[deleted]

Re: The N-Queens completion problem is NP-hard

#17

Post by andy_ppp » Mon, Sep 04, 2017, 4:52 PM UTC

Can you find an algorithm to a problem that many believe would show that P == NP? Probably not.

Re: The N-Queens completion problem is NP-hard

#18

Post by School-Cotton » Mon, Sep 04, 2017, 4:57 PM UTC

andy_ppp wrote: post #17

Can you find an algorithm to a problem that many believe would show that P == NP? Probably not.

It's not just "believed" that showing a polynomial-time algorithm for an NP-complete problem shows that P=NP; it's proven (in fact, this is part of the definition of NP-complete...)

Re: The N-Queens completion problem is NP-hard

#19

Post by School-Cotton » Mon, Sep 04, 2017, 4:57 PM UTC

cperciva wrote: post #13

School-Cotton wrote: post #12

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 s…

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.

Yep, sorry, edited my post.

Re: The N-Queens completion problem is NP-hard

#20

Post by School-Cotton » Mon, Sep 04, 2017, 4:58 PM UTC

Retric wrote: post #9

What you is fast in this case? If you can solve 1,000 x 1,000 in say 1 minute is that fast? Or do you need to solve 1,000,000 x 1,000,000 in a second?

The time it takes to solve needs to grow at most polynomially with the length of the representation of the input.