3 ms·

Is counting the number of solutions for a given n known to be NP-hard? And is finding any solution for a given n known to be in P? I saw a paper that found so

Is counting the number of solutions for a given n known to be NP-hard? And is finding any solution for a given n known to be in P? I saw a paper that found solutions up to 500,000 using a probabilistic method but wasn't sure if it was definitively proven to be in P or not.

CJefferson 5y ago
Checking if a partially filled in n-queens problem has a solution at all is NP complete. It might be there is an easy way of counting solutions for an empty grid, but usually the way we count solutions is divide and conquer, by giving different computers partially filled in grids.
- kevinwang 5y ago
  Interesting, so we don't know that it's np hard, but we basically assume it is? Do you know if anyone has tried to prove that it is?
  - CJefferson 5y ago
    NP-hardness is about yes/no questions, and we already know thwre is an answer to all n-queens instances except 2 and 3 :) It also can't really be #P (which is to do with hardness of counting), as that has to do with "input problem size", and N-queens with an empty grid doesn't have enough structure (as it's just a number) -- this is hard to explain in full in a short message :)
    - bjourne 5y ago
      But you can easily phrase it as an NP-hard problem: Are there at least X unique solutions to a board of particular size?
CaptainNegative 5y ago
Technically the answer to the second question is "no" when n is given in binary. As a valid output is Omega(n log n) bits in length, we can't hope to construct a solution in time polynomial in the input size, i.e. time poly(log n). However, when n is given in unary (meaning we have poly(n) time to find and output a solution), there is a 19th century German-language paper by Pauls that explicitly and efficiently constructs an n-queens solution for all n>3. So the unary version of the problem is in FP (the search version equivalent of P). tl;dr a solution to n-queens can be found in deterministic poly(n) time.

CJefferson 5y ago

Checking if a partially filled in n-queens problem has a solution at all is NP complete. It might be there is an easy way of counting solutions for an empty grid, but usually the way we count solutions is divide and conquer, by giving different computers partially filled in grids.

kevinwang 5y ago
Interesting, so we don't know that it's np hard, but we basically assume it is? Do you know if anyone has tried to prove that it is?
- CJefferson 5y ago
  NP-hardness is about yes/no questions, and we already know thwre is an answer to all n-queens instances except 2 and 3 :) It also can't really be #P (which is to do with hardness of counting), as that has to do with "input problem size", and N-queens with an empty grid doesn't have enough structure (as it's just a number) -- this is hard to explain in full in a short message :)
  - bjourne 5y ago
    But you can easily phrase it as an NP-hard problem: Are there at least X unique solutions to a board of particular size?

CaptainNegative 5y ago

Technically the answer to the second question is "no" when n is given in binary. As a valid output is Omega(n log n) bits in length, we can't hope to construct a solution in time polynomial in the input size, i.e. time poly(log n). However, when n is given in unary (meaning we have poly(n) time to find and output a solution), there is a 19th century German-language paper by Pauls that explicitly and efficiently constructs an n-queens solution for all n>3. So the unary version of the problem is in FP (the search version equivalent of P). tl;dr a solution to n-queens can be found in deterministic poly(n) time.