gkatsi

12 ms·

1. 1.▲
   by gkatsi 13y ago

   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
2. 2.▲
   by gkatsi 13y ago

   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 s
3. 3.▲
   by gkatsi 13y ago

   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