Computational complexity of recursion in prologue
I have 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 a list of items to 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 equal X = (1,2,3)
, and the complexity of finding the set O(n)
. Now I can type in ;
an alternative to make sure there is no other answer. Obviously not, and the script will return false
. My question is, what is the computational complexity of the second run of the script and why?
source to share
In your program, looking for the first answer is exponentially worst case. And it is quadratic at best.
Here's a specific query that takes exponentially many conclusions:
?- 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 difficulty for Goal, false
(if the program is essentially a pure Prolog program) than to determine the difficulty of finding only the first answer. The reason is that the former is independent of the exact order of the articles. Both of them depend on the order of the goals.
Refer to this answer for a lower bound justification.
Edit: Probably the most interesting note: if you want to fix this problem, that is, if you want to reduce the number of pins executed, you need to change something in the visible part of the failure slice.
source to share