On Fri, 30 Sep 2011, Sergey Dymchenko wrote: > Any hints how to estimate computational complexity (like Big-O > notation) of CLP programs? I mean there is no visible cycles, not > clear how pruning reduces complexity (does it really reduce in > asymptotic sense?) etc... It's rare for nontrivial CLPs to be provably anything less than exponential. In order to get a precise time bound you need to have a very good understanding of just how much pruning occurs in your particular problem; but it has to be a LOT (i.e. pruning at all but an at most logarithmic number of choice points) in order for the time to be polynomial. Number of options per variable to the power of the number of variables is a very loose upper bound for complete search. Searches that are not complete (such as credit search) can be proven a bit faster than that, at the cost of not necessarily being able to find an answer even if one exists. -- Matthew Skala mskala_at_ansuz.sooke.bc.ca People before principles. http://ansuz.sooke.bc.ca/Received on Fri Sep 30 2011 - 14:05:34 CEST
This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET