Re: [eclipse-clp-users] Computational complexity

Hi,

There are additional complications for any consideration of 
computational complexity, because the constraint propagation is itself a 
computation, and thus have a computational cost associated with it. It 
is when the cost of constraint propagation is less than the amount of 
computation saved by reducing the search space that using constraint wins.

Also, if you are trying to find a feasible solution, then using 
heuristics in your search can be very important in reducing the 
computation in finding the answer, but using different heuristics should 
not change the computational complexity, because you are still searching 
the same search-space.

Cheers,

Kish

On 30/09/2011 16:51, Marco Gavanelli wrote:
> 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
>


-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.