Prolog的时间复杂性比天真的暴力更好吗？

在(最好的)Prolog中解决任何问题的时间复杂性是否比天真的强力回溯实现更好？

我说Prolog语言一般......我想知道是否有一些众所周知的算法,例如使用Scheme中的call/cc回溯来做'Prolog'是一个糟糕的选择.

编辑:通过"解决任何问题"我的意思是所有Prolog程序."问题中的问题":我对语言设计感到疑惑:如果完全延续对部分延续具有任何实际效用(主要优点是Prolog-esque,但如果它们无法在时间复杂性上竞争则不是很严重使用Prolog),如果另一种语言可以完全吸收Prolog,或者通过将程序限制为Prolog形式(类似于Fortran over C中可能的优化),可以实现优化.

编辑:按时间复杂度我的意思是大O,即修剪不可能用一般语言模仿Prolog.

当它被字面翻译成Prolog 时,天真的暴力搜索将仍然是一个天真的暴力搜索 .

没关系:Plain Prolog非常适合描述和运行强力搜索.尽管如此,你仍然可能无法用Prolog编写的强力搜索击败任何暴力搜索的手动优化低级版本.另一方面,Prolog的输入非常简单方便,你可能很快会找到更好的搜索策略并进行一些原型设计,而这些其他策略通常会轻易击败任何暴力实施.即使在天真地翻译时,Prolog也非常擅长回溯,并且在一些(更小或更大,取决于您使用的Prolog实现)的低级代码因素中有效.

然而,在描述搜索问题时,Prolog与许多其他语言相比具有的主要优势是约束:由于所谓的约束传播,搜索空间通常可以被显着且自动地修剪.您不需要特殊规定:约束求解器将为您完成.

约束的承诺,以及承诺在很大程度上变为现实,是(1)您陈述要求和(2)Prolog引擎为您找到解决方案.查看clpfd,了解该方案的一个非常重要的实例.

因此,我提出了一个问题:在任何语言中,将天真蛮力搜索转换为更明智的搜索策略有多容易？毕竟,这就是通常可以实现真正重大改进的方式.

在Prolog中,答案通常是:非常简单.在大多数其他语言中,没有那么多.