[SOLVED] Computational complexity of recursion in prolog

Computational complexity of recursion in prolog

I've got a recursion:

list_to_set([],[]).

list_to_set([A|X],[A|Y]):-
   list_to_set(X,Y),
    \+member(A,Y).

list_to_set([A|X],Y):-
   list_to_set(X,Y),
   member(A,Y).

It converts list of elements into a set. For example [1,1,2,3] -> [1,2,3]. When I enter the query list_to_set([1,1,2,3],X). the result is X = (1,2,3) and the complexity of finding out the set is O(n). Now I can type ; alternative to make sure, that there is no other possible answer. Obviously there is none and script will return false. My question is: what is the computational complexity of that second script run, and why?

Solution

With your program, finding the first answer is exponential in the worst case. And it is quadratic in the best case.

Here is a concrete query that takes exponentially many inferences:

?- length(L,N),maplist(=(a),L),time(once(list_to_set(L,S))).
   ...
;  % 1,310,714 inferences, 0.180 CPU in 0.180 seconds (100% CPU, 7288089 Lips)
   L = [a,a,a,a,a,a,a,a,a|...], N = 18, S = [a]
;  % 2,621,434 inferences, 0.337 CPU in 0.337 seconds (100% CPU, 7789752 Lips)
   L = [a,a,a,a,a,a,a,a,a|...], N = 19, S = [a]
; ... .

It is usually easier to determine the complexity for Goal, false (provided the program is essentially a pure Prolog program) than it is to determine the complexity to find the first answer only. The reason is that the former is independent of the precise order of clauses. Both depend on the order of goals, though.

Please refer to this answer for a justification for a lower bound.

Edit: Maybe the most interesting observation is this: If you want to fix this problem, that is if you want to reduce the number of inferences performed, you have to change something in the visible part of the failure slice.