Complejidad de predicados ISO Prolog

time-complexity iso-prolog

Question

¿Hay alguna garantía para los límites superiores en la complejidad temporal de los predicados Prolog estándar?

Por ejemplo: ¿es seguro que sort(+List, ?SortedList) ejecuta en tiempo O (nlog (n)) (siendo n la longitud de List ) en cualquier sistema Prolog compatible estándar?

Answer 1

tl; dr: No y no.

Comencemos con sort/2 que idealmente necesitaría n ld ( n ) comparaciones. Bien, pero ¿cuánto tiempo lleva una comparación? Probemos esto:

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).

En SICStus 4.3.1 y 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

Al duplicar el tamaño, podemos estimar fácilmente cuál será el tiempo de ejecución. Si también se duplica, es lineal, y si se cuadruplica es cuadrático. Claramente, ambos tienen al menos tiempo de ejecución cuadrático.

Es posible que se describa el tiempo de ejecución preciso de manera abstracta, pero es muy difícil asegurarse de que todo esté bien. En cualquier caso, es casi imposible ordenar una promesa concreta en un documento estándar. Además, es muy difícil validar tales afirmaciones.

La mejor medida abstracta podría ser el número de inferencias, a menudo se pueden observar fácilmente. Ver el mayor entero o factors . Pero, de nuevo, esto es solo una medida abstracta, por lo que algo ha sido arrancado, abstraxit . Es muy posible que también se hayan eliminado las características clave.

En general, el estándar ISO ISO / IEC 13211-1: 1995 core, no exige ninguna garantía para las complejidades de tiempo de ejecución que están claramente fuera del alcance. Menciona explícitamente en una nota que también los límites de recursos están fuera de alcance:

1 Alcance

....

NOTA - Esta parte de ISO / IEC 13211 no especifica:

a) el tamaño o la complejidad del texto de Prolog que excederá el
capacidad de cualquier sistema o lenguaje de procesamiento de datos específico
procesador, o las acciones a tomar cuando el correspondiente
se exceden los límites;
...

Recuerde siempre que un estándar técnico es una condición previa para garantizar que un sistema sea apto para algún propósito. No es una condición suficiente. Vea el ejemplo bajo Propósito en esta respuesta para un ejemplo algo extremo.