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."
That's just a good heuristic, though, it does not guarantee finding a solution. Also note that NP is a class of decision problems, and finding a solution for the n-Queens problem is not.
None of the two decision problems that arise naturally from n-queens, deciding whether there exists solutions for a given board size, and verifying whether a candidate is indeed a solution, are NP-hard (solutions exist for n \not\in {2, 3}; verification can clearly be done in time quadratic in n). Counting solutions is #P-complete, though.
If you read the cites on that link, you'll see that the value for 26 was only added in 2016. They do not have a closed form formula, or they would have shown it.
I mean, they could just be slow revealing. I doubt it, though.
Do you mean that it's #P and not a priori NP? Counting problems can sometimes be in NP by deciding whether the count is the correct one (with the right encoding, function problems can be thought of as a subset of decision problems).
A not too silly example is counting partitions: the number of ways of writing a positive integer as a sum of non-decreasing positive integers (like 5=3+2 or 5=4+1 or 5=2+2+1). There's a dynamic programming solution with running time within O(n^3), so it is definitely in NP.
In another comment you mention that finding a solution to n-queens is not NP because it's not a decision problem. I'm confused because I thought the solution would be the polynomial certificate to the problem "an nxn board can be filled with n mutually non-threatened queens."
> Do you mean that it's #P and not a priori NP? Counting problems can sometimes be in NP by deciding whether the count is the correct one (with the right encoding, function problems can be thought of as a subset of decision problems). It is unlikely that a #P-complete problem
Essentially, #P is the class of problems where you compute the number of accepting runs for some problem in NP, so yes, #P and NP are closely related.
You can turn a counting problem into a decision problem by a suitable encoding, but that turns it into a different problem (and the complexity depends on the encoding). The more natural fit for a class of decision problems corresponding to #P would be PP, the class of problems where the majority of runs on a probabilistic TM accepts, which contains NP.
> In another comment you mention that finding a solution to n-queens is not NP because it's not a decision problem. I'm confused because I thought the solution would be the polynomial certificate to the problem "an nxn board can be filled with n mutually non-threatened queens."
The point is that deciding whether there is a solution is not NP-hard (it is in NP though, precisely by your argument that a solution is the polynomial certificate that can be verified in polynomial time). Indeed, existence of a solution can be decided in constant time (and is thus in P), since there are solutions whenever n is neither 2 nor 3. Furthermore, for any given n (except 2 and 3), a solution can be constructed explicitly in linear time (for a unary encoding of n). Nevertheless, counting solutions is hard.
Yes, changing the encoding can change the complexity, but I was taking issue with "because it is #P it cannot be NP,' which is what I got out of
> Counting solutions is not a decision problem, so it can't be in NP.
Is this just a statement that it is a category error to compare the set of function problems with the set of decision problems? Sure, that's true, but you can still ask questions like "does this #P problem have a polynomial reduction to an NP problem."
> Nevertheless, counting solutions is hard
Do you have a citation for counting n-queens solutions (not completions like in the featured paper) being #P-hard? (or NP-hard?)
> Sure, that's true, but you can still ask questions like "does this #P problem have a polynomial reduction to an NP problem."
That's an ill-posed question though. NP is not closed under polynomial Turing reductions (otherwise we had NP = coNP), so some problem Q being polynomially Turing-reducible to some other problem S in NP does not tell you anything about the complexity of Q. Other notions of polynomial reductions, in particular polynomial many-one reductions, don't apply, because the require both problems to be decision problems. So while you can indeed ask such a question, it doesn't make much sense to do so.
Coming back to the problem at hand, consider what a polynomial certificate would look like that assures that no further solutions existed (if “does the n-queens problems have exactly m solutions” were in NP, such a certificate must exist), and how it could be verified in polynomial time (i.e., without checking each other solution candidate).
> Do you have a citation for counting n-queens solutions (not completions like in the featured paper) being #P-hard? (or NP-hard?)
> "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