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 : 0472186443Received on Mon Oct 03 2011 - 08:08:44 CEST
This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET