ISO Prolog 谓词的复杂性

Question

标准 Prolog 谓词的时间复杂度的上限是否有任何保证？

例如：是否确定 sort(+List, ?SortedList) 在任何符合标准的 Prolog 系统中运行 O(nlog(n)) 时间（n 是 List 的长度）？

Answer 1

tl;dr：没有也没有。

让我们从 sort/2 开始，理想情况下需要 n ld(n) 比较。很好，但是一次比较需要多长时间？让我们试试看：

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

在 SICStus 4.3.1 和 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

通过复制大小，我们可以轻松估计运行时间。如果它也重复，它是线性的，如果它是四倍的，它是二次的。显然两者都至少有二次运行时间。

以抽象的方式描述精确的运行时间是可能的，但很难确保一切正常。无论如何，在标准文件中强制执行具体承诺几乎是不可能的。而且，要证实这样的说法是非常困难的。

最好的抽象度量可能是推理的数量，通常它们很容易观察到。参见 the largest integer or factors。但同样，这只是一个抽象的措施 - 所以有些东西被撕掉了，abstraxit。很可能关键特征也被撕掉了。

一般来说，ISO 标准 ISO/IEC 13211-1:1995 核心不要求对明显超出范围的运行时复杂性提供任何保证。它在注释中明确提到资源限制也超出范围：

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

永远记住，技术标准是确保系统适合某些用途的先决条件。这不是充分条件。请参阅 this answer 中 Purpose 下的示例，了解一个稍微极端的示例。

ISO Prolog 谓词的复杂性

Complexity of ISO Prolog predicates

prolog

time-complexity

iso-prolog

1 Scope