4 ms·

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 encodin

by 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.”

by kmill 9y ago

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.”