Complexity in Prolog programs?

Question

In Prolog, problems are solved using backtracking. It's a declarative paradigm rather than an imperative one (like in C, PHP or Python). In this kind of languages is it worth to think in terms of complexity?

The natural way you think problems seems to be O(N^2) as someone pointed in this question.

Answer 1

You can definitely analyze the complexity of Prolog programs, just like any other language. That particular problem you linked might be O(n^2). But not all Prolog programs will have this complexity. For example, you can easily write a SAT solver in Prolog, and that problem is NP-Complete.

Answer 2

It entirely depends on the problem.

e.g. summing a list of numbers is O(N), as far as I can tell.

sum([],0).
sum(List,Total) :-
   sum(List,0,Total).

sum([],Total,Total).
sum([Head|Rest],Accumulator,Total) :-
    SoFar is Head + Accumulator,
    sum(Rest,SoFar,Total).

The only actions are the addition ("is") and the recursive call, which should both be worth 1 each. They'll both be performed ~ once per item in the list, so the total actions should be ~ 2N, which is O(N).

Answer 3

Its important to analyze Complexity in any Language be it prolog or any imperative language. However I can give you some tips to speed up your prolog programs

1. Always Always try to make your programs tail recursive. This will ensure that your program doesnt run out of stack.
2. Try to use cut and fail in your programs where you know you dont need any further answers.
3. Try using accumalators.
4. Check out CLPFD, It helps in reducing the search space drastically which speeds up your program. Essentially it eliminates the bad choice before your program can backtrack and wasting time exploring those choices.
5. Always write the best outcome rule first. (This really depends on the problem , but generally best case rule goes first).