On 30/09/11 14:49, Sergey Dymchenko wrote: > Hello! > > 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... Hi, I think it is not clear what you mean exactly. CLP itself is a superset of Prolog, which is Turing complete, so you can write programs of any complexity: it depends on the program you write. However, CLP is often used to solve CSP problems. CSPs are NP-complete problems, so there is no known algorithm less than exponential, so every program (including a CLP program) that solves is (nowadays) is exponential. If you have a CSP with N variables ranging on domains of size D, then the search space has size D^N. However, if, thanks to constraint propagation, you are able to halve the domains, the search space becomes D^N/2^N, so you got an exponential speedup. But depending on the problem, you could have no propagation at all, so it really depends on the problem you are considering. Cheers, Marco -- Marco Gavanelli, Ph.D. in Computer Science Dept of Engineering University of Ferrara Tel/Fax +39-0532-97-4833 http://www.ing.unife.it/docenti/MarcoGavanelli/Received on Fri Sep 30 2011 - 15:51:50 CEST
This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET