Re: [eclipse-clp-users] Computational complexity

From: Marco Gavanelli <marco.gavanelli_at_unife.it>
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...

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