7 ms·

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.

mmarx 9y ago
Counting solutions is not a decision problem, so it can't be in NP. The corresponding counting complexity class is #P.
- kmill 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). 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 ago
    Finding a polynomial algorithm for #P problem implies P=NP.
    - kmill 9y ago
      Surely 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 ago
      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?)
      - mmarx 9y ago
        > 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?) Jieh Hsiang, D.Frank Hsu, Yuh-Pyng Shieh, On the hardness of counting problems of complete mappings, Discrete Mathematics, Volume 277, Issue 1, 2004, Pages 87-100, ISSN 0012-365X, http://dx.doi.org/10.1016/S0012-365X(03)00176-6 http://dx.doi.org/10.1016/S0012-365X(03)00176-6. (http://www.sciencedirect.com/science/article/pii/S0012365X03001766 http://www.sciencedirect.com/science/article/pii/S0012365X03...) Note that they assume a binary encoding of n, and hence get “beyond #P.”
anonetal 9y ago
Actually 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 ago
  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.
  - 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 ago
      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.
      - thomasahle 9y ago
        Computational hardness doesn't depend on whether anybody knows an efficient algorithm. Just whether one exists.

mmarx 9y ago

Counting solutions is not a decision problem, so it can't be in NP. The corresponding counting complexity class is #P.

kmill 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). 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 ago
  Finding a polynomial algorithm for #P problem implies P=NP.
  - kmill 9y ago
    Surely 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 ago
    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?)
    - mmarx 9y ago
      > 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?) Jieh Hsiang, D.Frank Hsu, Yuh-Pyng Shieh, On the hardness of counting problems of complete mappings, Discrete Mathematics, Volume 277, Issue 1, 2004, Pages 87-100, ISSN 0012-365X, http://dx.doi.org/10.1016/S0012-365X(03)00176-6 http://dx.doi.org/10.1016/S0012-365X(03)00176-6. (http://www.sciencedirect.com/science/article/pii/S0012365X03001766 http://www.sciencedirect.com/science/article/pii/S0012365X03...) Note that they assume a binary encoding of n, and hence get “beyond #P.”

anonetal 9y ago

Actually 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 ago
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.
- 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 ago
    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.
    - thomasahle 9y ago
      Computational hardness doesn't depend on whether anybody knows an efficient algorithm. Just whether one exists.