7 ms·
The N-Queens completion problem is NP-hard
- anonetal 9y agoThe 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.
- deleted 9y ago[deleted]
- cropsieboss 9y agoDamn 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.
- mmarx 9y agoCounting solutions is not a decision problem, so it can't be in NP. The corresponding counting complexity class is #P.
- kmill 9y agoDo 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."
- cropsieboss 9y agoFinding a polynomial algorithm for #P problem implies P=NP.
- kmill 9y agoSurely you mean finding a polynomial algorithm for a #P-complete problem?
- mmarx 9y ago> 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.
- kmill 9y agoYes, 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?)
- anonetal 9y agoActually the queens problem starting with an empty board is not NP-Hard. See: https://cstheory.stackexchange.com/questions/12682/is-the-n-queens-problem-np-hard 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.
- mmarx 9y agoThat'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.
- thomasahle 9y ago> Counting solutions is #P-complete, though. Are you sure? Where was this proven? It could easily be that http://oeis.org/A000170 http://oeis.org/A000170 had a polynomial time combinatorial formula. Maybe some completion-counting problem could be shown to be #P-complete though.
- taeric 9y agoIf 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.
- thomasahle 9y agoComputational hardness doesn't depend on whether anybody knows an efficient algorithm. Just whether one exists.
- chch 9y agoIf 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.html 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 http://jair.org/papers/paper5512.html " [3] http://jair.org/papers/paper5512.html http://jair.org/papers/paper5512.html
- deleted 9y ago[deleted]
- MichaelBurge 9y agoYou can also claim the $1 million by being good at Mario and explaining your techniques: https://arxiv.org/abs/1203.1895 https://arxiv.org/abs/1203.1895
- avaer 9y agoOnly if you are provably, mathematically good at Mario. Not just you seem to do well over the course of a measly billion games of.
- sabujp 9y agoahh nqueens, this was my first real parallel program that I did using mpi
- Retric 9y agoWhat 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?
- umanwizard 9y agoThe time it takes to solve needs to grow at most polynomially with the length of the representation of the input.
- Retric 9y agoThe input is just a single number. So grow polynomial from N x N board size? I really don't get how this is equivalent to NP.
- pg_is_a_butt 9y agowow... if you don't get it, then P=NP. you did it. you're all idiots.
- CarolineW 9y agoYou either read the earlier version before it was corrected, or you're misunderstanding. The problem is not the N-Queens problem, it's the N-Queens /completion/ problem. The problem is this: Here's an NxN board with k queens already placed. Is there a way to place another N-k queens so they are all mutually non-attacking? Most instances will be easy, but current algorithms to solve this are such that for each N, the time taken in the worst case is an exponential function of N.
- Retric 9y agoAhh, thanks it looks like it was changed after I read it.
- fooker 9y agoYou have to be P=NP fast. ;)
- umanwizard 9y agoThe 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.
- andy_ppp 9y agoCan you find an algorithm to a problem that many believe would show that P == NP? Probably not.
- umanwizard 9y agoIt'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...)
- imaginenore 9y agoIt's currently solved for up to N=27 Both 26 and 27 solutions came from supercomputers/FPGAs and took months of compute time. http://www.nqueens.de/sub/WorldRecord.en.html http://www.nqueens.de/sub/WorldRecord.en.html
- chengsun 9y agoNo, you're talking about a different problem: that of counting the total number of n-queens solutions. The original article is talking about the problem of deciding, given a partial placement of queens, whether it can be completed by adding further queens to form an n-queen solution.
- deleted 9y ago[deleted]
- master_yoda_1 9y agoThanks for telling me that :)
- rdiddly 9y agoCompletely off-topic: As a one-time civil engineer, mathematical dullard, and frequent New York visitor, who is losing his mind, I thought this was about completing a subway line. In my defense, the N train does go to Queens (though it's not called the N-Queens), and everybody knows completing a subway line is a really hard problem, especially if you're following the story of the new 2nd Ave line.
- Zarathust 9y agoIs there a proof somewhere which states that all NP hard problem can have a similar / generic solution? I find it more likely that the N-Queens problem will have a very specific solution
- pdpi 9y agoProblems in NP hard that are also in NP are known as NP-complete. NP complete problems share the characteristic that all problems in P can be reduced to any NP problem in polynomial time (which is to say: you can encode P problems as particular instances of NP problems). Therefore, if P = NP, all problems in NP are reducible to one another.
- mathieubordere 9y agoI don't get why this article is getting attention here.