gkatsi · HackerTrans

vor 13 Jahrendiscuss

It is NP-complete in the weak sense: the reduction from, say, CNF-SAT, introduces very large coefficients (in the order of 2^n). The pseudo-polynomial algorithm has complexity linear in the magnitude of the coefficients, not in the size of their binary representation (hence pseudo). If the coefficients are small, that algorithm is efficient. See: http://en.wikipedia.org/wiki/Pseudo-polynomial_time

gkatsi

vor 13 Jahrendiscuss

It is not, because it is a single linear equality and all variables are >= 0. This is not just nitpicking: solving Diophantine problems is in general undecidable, but this problem can be solved in pseudo-polynomial time (linear in the sum of all coefficients)

gkatsi

vor 13 Jahrendiscuss

I think it is a mistake to try to characterize when CP works based on constrainedness or on the number of solutions. In fact, being loosely constrained is typically used to imply that a problem is easy. The problem for CP is when a problem is NOT loosely constrained, but propagation is weak. This means that whatever reasoning we can do with the set of constraints, we cannot express as value prunings.

As for the number of solutions vs constrainedness: as far as I know, the only domain in which there exists a clear theoretical understanding of number of solutions vs difficulty is random problems, where we see an "easy-hard-less hard" pattern as we increase the density for a fixed size problem. What happens there is that there is an exponential number of solutions in the easy region which form a small (polynomial number) of very big clusters. As we get to the hard region, the number of solutions remains exponential, but the solution space shatters into an exponentially large number of clusters. The definition of a cluster in this case is: if two solutions have constant Hamming distance, they are in the same cluster. On the other hand, some unsatisfiable problems (so 0 solutions) are very very hard for CP and related approaches.

All this is just to say that the picture is much more complicated than you say and the best way to figure out if CP is a good fit for an application is to try it. People develop intuition over time of course, but the issue is far from understood.

comments