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?

Reichert

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.

Interatomic

The answer misses the point somewhat. Clearly, the OP wonders whether there is a guarantee for the complexity of the sorting algorithm, which in all literature is given under the assumption of constant time comparison. – Tew

Please reread the question: It is not about the algorithm of sorting as such, but about sort/2. – Interatomic

In your timings, you double the list length and at the same time double the average element size. I.e. you quadruple the data to be sorted and then observe a 4-5fold increase in runtime. This is neither a conventional way of measuring the complexity of sorting, nor is it correct to talk about quadratic complexity (that would require an N^2 term). – Tew

@jschimpf: Please reread to OP's question: It's about whether not it is certain that sort/2 runs O(n ld n). And I gave an example where this boundary does not hold, because that formula does not take into account the size of the arguments. – Interatomic