Re: [eclipse-clp-users] Computational complexity

From: <mskala_at_ansuz.sooke.bc.ca>
Date: Fri, 30 Sep 2011 08:54:39 -0500 (CDT)
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