prolog - ISO Prolog 谓词的复杂性

Question

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

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

Answer 1

tl;dr:不，不。

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

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

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

以抽象的方式描述精确的运行时间是可能的，但很难确保一切正常。无论如何，在标准文件中强制执行具体的 promise 几乎是不可能的。此外，很难验证此类声明。

最好的抽象度量可能是推理的数量，它们通常很容易观察到。请参阅 the largest integer 或 factors 。但同样，这只是一个抽象的衡量标准——所以有些东西被撕掉了，抽象的。很可能关键功能也被撕掉了。

一般来说，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 中 目的 下的示例，了解一个有点极端的示例。