ISO Prolog谓词的复杂性

Question

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

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

Answer 1

tl;博士:不,不.

让我们从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

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

以抽象的方式描述精确的运行时可能是可能的,但很难确保一切都很好.无论如何,在标准文件中强制要求具体承诺几乎是不可能的.此外,验证此类声明非常困难.

最好的抽象度量可能是推论的数量,通常可以很容易地观察到.查看最大的整数或因子.但同样,这只是一个抽象的衡量标准 - 所以有些事情已被撕掉,abstraxit.情况很可能也是关键特征已被撕掉.

一般而言,ISO标准ISO/IEC 13211-1:1995核心并未要求对运行时复杂性提出任何保证,这些复杂性明显超出范围.它在一个说明中明确提到资源限制也超出了范围:

1范围

....

注 - ISO/IEC 13211的本部分未规定:

a)Prolog文本的大小或复杂性将超过
任何特定数据处理系统或语言
处理器的容量,或
超出相应限制时应采取的措施;
...

永远记住,技术标准是确保系统适合某种目的的先决条件.这不是一个充分的条件.参见下的示例目的在这个答案对于一个有点极端的例子.