Complexity of ISO Prolog predicates

Question

Are there any guarantees for upper bounds on the time complexity of the standard Prolog predicates?

For example: is it certain that sort(+List, ?SortedList) runs in O(nlog(n)) time (n being the length of List) in any standard compliant Prolog system?

Answer 1

tl;dr: No and no.

Let's start with sort/2 which ideally would need n ld(n) comparisons. Fine, but how long does one comparison take? Let's try this out:

tails(Es0, [Es0|Ess]) :-
   Es0 = [_|Es],
   tails(Es, Ess).
tails([],[[]]).

call_time(G,T) :-
   statistics(runtime,[T0|_]),
   G,
   statistics(runtime,[T1|_]),
   T is T1 - T0.

| ?- between(12,15,I), N is 2^I, length(L,N),maplist(=(a),L),
     tails(L,LT), call_time(sort(LT,LTs), Tms).

On SICStus 4.3.1 and SWI 7.1.28

I = 12, N = 4096,   Tms_SICS =   680,  Tms_SWI =   3332
I = 13, N = 8192,   Tms_SICS =  2800,  Tms_SWI =  14597
I = 14, N = 16384,  Tms_SICS = 11300,  Tms_SWI =  63656
I = 15, N = 32768,  Tms_SICS = 45680,  Tms_SWI = 315302

By duplicating the size we can easily estimate what the runtime will be. If it duplicates as well, it is linear, and if it quadruples it is quadratic. Clearly both have at least quadratic runtime.

Describing the precise runtime in an abstract manner might be possible, but it is very difficult to ensure that everything is fine. In any case, it is next-to-impossible to mandate a concrete promise in a standard document. Also, it is very difficult to validate such claims.

The best abstract measure might be the number of inferences, often they can be easily observed. See the largest integer or factors. But again, this is only an abstract measure - so something has been torn away, abstraxit. It might very well be the case that the key features have been torn away too.

In general, the ISO standard ISO/IEC 13211-1:1995 core, does not mandate any guarantee for runtime complexities which are clearly out of scope. It mentions explicitly in a note that also resource limits are out of scope:

1 Scope

....

NOTE — This part of ISO/IEC 13211 does not specify:

a) the size or complexity of Prolog text that will exceed the
capacity of any specific data processing system or language
processor, or the actions to be taken when the corresponding
limits are exceeded;
...

Always remember that a technical standard is a precondition to ensure that a system is fit for some purpose. It is not a sufficient condition. See the example under Purpose in this answer for a somewhat extreme example.