3 ms·

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

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.
      - taeric 9y ago
        Fair enough. I was obviously reading the above as having a polynomial time as having an efficient time one. Where efficient was shorthand for "quick." Both leaps, I concede were misguided.

3 ms·

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

by anonetal 9y ago

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.
      - taeric 9y ago
        Fair enough. I was obviously reading the above as having a polynomial time as having an efficient time one. Where efficient was shorthand for "quick." Both leaps, I concede were misguided.