Re: [eclipse-clp-users] Computational complexity

Hi all,
Marco is right.

Furthermore, beside big-O which is the worst case,we're  founded  to ask rather : what is the big-Omega (lower bound) or Theta (almost equality).
I put aside the "average case" which is often harder to compute than the problem itself  
Think of Quick-sort which is O(N^2) in the worst case but much less in his average case. Writing Q-sort in CLP/CSP stays O(N^2). The worst case is when the data is already sorted, no matter how you choose the "pivot".

Regards
Alex


Le 30 sept. 2011 à 17:51, Marco Gavanelli a écrit :

> 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/
> 
> ------------------------------------------------------------------------------
> All of the data generated in your IT infrastructure is seriously valuable.
> Why? It contains a definitive record of application performance, security
> threats, fraudulent activity, and more. Splunk takes this data and makes
> sense of it. IT sense. And common sense.
> http://p.sf.net/sfu/splunk-d2dcopy2
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users

 -------------------------------
Alexandre Saidi
Maitre de Conférences
Ecole Centrale de Lyon-Dép. MI
LIRIS-CNRS UMR 5205
Tél : 0472186530, Fax : 0472186443