|
|
|
|
|
|
by kmill
3212 days 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?) |
|
|
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://www.sciencedirect.com/science/article/pii/S0012365X03...)
Note that they assume a binary encoding of n, and hence get “beyond #P.”