Re: [eclipse-clp-users] Computational complexity

From: Marco Gavanelli <marco.gavanelli_at_...17...>
Date: Fri, 30 Sep 2011 17:51:41 +0200
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...


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.


Marco Gavanelli, Ph.D. in Computer Science
Dept of Engineering
University of Ferrara
Tel/Fax  +39-0532-97-4833
Received on Fri Sep 30 2011 - 15:51:50 CEST

This archive was generated by hypermail 2.2.0 : Mon Jul 09 2018 - 02:05:29 CEST